scientific article; zbMATH DE number 1048047

Publication date: 22 September 1997

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

tiling complexity classes combinatorial reductions deterministic exponential time lowerbound encoding machine computations hardness of combinatorial problems Hilbert 10 reduction master reductions reduction chain to the knapsack problem satisfiability in propositional dynamic logic

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Combinatorial aspects of tessellation and tiling problems (05B45) Turing machines and related notions (03D10)

Related Items (48)

On the Decidability of Elementary Modal Logics ⋮ Which XML schemas are streaming bounded repairable? ⋮ Decidability and complexity of action-based temporal planning over dense time ⋮ On Composing Finite Forests with Modal Logics ⋮ Turing Machines for Dummies ⋮ Tilings: recursivity and regularity ⋮ A logical approach to locality in pictures languages ⋮ Consensus Game Acceptors ⋮ Complexity of question/answer games ⋮ Fast domino tileability ⋮ Unnamed Item ⋮ On the freeze quantifier in Constraint LTL: Decidability and complexity ⋮ Branching-time logics with path relativisation ⋮ Extending inclusion dependencies with conditions ⋮ On simplification of schema mappings ⋮ Bounded repairability of word languages ⋮ The tail-recursive fragment of timed recursive CTL ⋮ Are bundles good deals for first-order modal logic? ⋮ On keys and functional dependencies as first-class citizens in description logics ⋮ Linear Programming Tools for Analyzing Strategic Games of Independence-Friendly Logic and Applications ⋮ Computational aspects of M. C. Escher's ribbon patterns ⋮ Martin Davis and Hilbert’s Tenth Problem ⋮ Consensus Game Acceptors and Iterated Transductions ⋮ Decidability and complexity of the fragments of the modal logic of Allen's relations over the rationals ⋮ On relative and probabilistic finite counterability ⋮ Infinite games with finite knowledge gaps ⋮ The monodic fragment of propositional term modal logic ⋮ Rewriting of regular expressions and regular path queries ⋮ Playing Savitch and Cooking Games ⋮ Finite-word hyperlanguages ⋮ LTL over integer periodicity constraints ⋮ Multi-buffer simulations: decidability and complexity ⋮ Closest substring problems for regular languages ⋮ Capacitated automata and systems ⋮ Unnamed Item ⋮ Decidable subsets of open logic and an algorithm for R-calculus ⋮ Model checking for hybrid branching-time logics ⋮ On the decidability of finding a positive ILP-instance in a regular set of ILP-instances ⋮ Tableau Method and NEXPTIME-Completeness of DEL-Sequents ⋮ From decidability to undecidability by considering regular sets of instances ⋮ On timeline-based games and their complexity ⋮ The Complexity of Model-Checking Tail-Recursive Higher-Order Fixpoint Logic ⋮ Query inseparability for \(\mathcal{ALC}\) ontologies ⋮ Reasoning about XML constraints based on XML-to-relational mappings ⋮ Frontier between decidability and undecidability: A survey ⋮ Logical separability of labeled data examples under ontologies ⋮ Undecidability of Multi-modal Hybrid Logics ⋮ A strip-like tiling algorithm

This page was built for publication: