scientific article; zbMATH DE number 1048047
zbMATH Open0874.03050MaRDI QIDQ4348133FDOQ4348133
Authors: Peter van Emde Boas 
Publication date: 22 September 1997
Title of this publication is not available (Why is that?)
Recommendations
complexity classestilingcombinatorial reductionsdeterministic exponential time lowerboundencoding machine computationshardness of combinatorial problemsHilbert 10 reductionmaster reductionsreduction chain to the knapsack problemsatisfiability in propositional dynamic logic
Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Combinatorial aspects of tessellation and tiling problems (05B45) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10)
Cited In (54)
- Exploring non-regular extensions of propositional dynamic logic with description-logics features
- Reasoning on data words over numeric domains
- Extended bounded response LTL: a new safety fragment for efficient reactive synthesis
- Playing Savitch and cooking games
- Martin Davis and Hilbert's tenth problem
- Satisfiability for SCULPT-schemas for CSV-like data
- Rewriting of regular expressions and regular path queries
- Query inseparability for \(\mathcal{ALC}\) ontologies
- Undecidability of multi-modal hybrid logics
- Title not available (Why is that?)
- Which XML schemas are streaming bounded repairable?
- Bounded repairability of word languages
- The monodic fragment of propositional term modal logic
- Decidability and complexity of the fragments of the modal logic of Allen's relations over the rationals
- Complexity analysis of propositional concurrent programs using domino tiling
- On relative and probabilistic finite counterability
- Frontier between decidability and undecidability: A survey
- Closest substring problems for regular languages
- Consensus game acceptors
- A logical approach to locality in pictures languages
- A strip-like tiling algorithm
- On the freeze quantifier in Constraint LTL: Decidability and complexity
- On the decidability of elementary modal logics
- On keys and functional dependencies as first-class citizens in description logics
- Title not available (Why is that?)
- Fast domino tileability
- Multi-buffer simulations: decidability and complexity
- The tail-recursive fragment of timed recursive CTL
- Decidable subsets of open logic and an algorithm for R-calculus
- Are bundles good deals for first-order modal logic?
- On the decidability of finding a positive ILP-instance in a regular set of ILP-instances
- Capacitated automata and systems
- From decidability to undecidability by considering regular sets of instances
- First-order temporal logic on finite traces: semantic properties, decidable fragments, and applications
- Tilings: recursivity and regularity
- The complexity of model-checking tail-recursive higher-order fixpoint logic
- Tableau method and NEXPTIME-completeness of DEL-sequents
- Computational aspects of M. C. Escher's ribbon patterns
- Reasoning about XML constraints based on XML-to-relational mappings
- Finite-word hyperlanguages
- Consensus game acceptors and iterated transductions
- Decidability and complexity of action-based temporal planning over dense time
- On Composing Finite Forests with Modal Logics
- LTL over integer periodicity constraints
- Turing machines for dummies. Why representations do matter
- Extending inclusion dependencies with conditions
- Complexity of question/answer games
- Title not available (Why is that?)
- On timeline-based games and their complexity
- Model checking for hybrid branching-time logics
- Branching-time logics with path relativisation
- On simplification of schema mappings
- Logical separability of labeled data examples under ontologies
- Infinite games with finite knowledge gaps
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4348133)
