scientific article; zbMATH DE number 1048047
From MaRDI portal
Publication:4348133
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)
Recommendations
Cited in
(54)- Rewriting of regular expressions and regular path queries
- Martin Davis and Hilbert's tenth problem
- Satisfiability for SCULPT-schemas for CSV-like data
- Playing Savitch and cooking games
- Query inseparability for \(\mathcal{ALC}\) ontologies
- Exploring non-regular extensions of propositional dynamic logic with description-logics features
- Which XML schemas are streaming bounded repairable?
- Undecidability of multi-modal hybrid logics
- scientific article; zbMATH DE number 7577569 (Why is no real title available?)
- 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
- On relative and probabilistic finite counterability
- Complexity analysis of propositional concurrent programs using domino tiling
- Frontier between decidability and undecidability: A survey
- Consensus game acceptors
- Closest substring problems for regular languages
- A logical approach to locality in pictures languages
- A strip-like tiling algorithm
- On the freeze quantifier in Constraint LTL: Decidability and complexity
- On keys and functional dependencies as first-class citizens in description logics
- On the decidability of elementary modal logics
- Fast domino tileability
- scientific article; zbMATH DE number 3894472 (Why is no real title available?)
- Multi-buffer simulations: decidability and complexity
- Decidable subsets of open logic and an algorithm for R-calculus
- The tail-recursive fragment of timed recursive CTL
- Are bundles good deals for first-order modal logic?
- Capacitated automata and systems
- On the decidability of finding a positive ILP-instance in a regular set of ILP-instances
- From decidability to undecidability by considering regular sets of instances
- Tilings: recursivity and regularity
- First-order temporal logic on finite traces: semantic properties, decidable fragments, and applications
- Reasoning on data words over numeric domains
- Computational aspects of M. C. Escher's ribbon patterns
- Tableau method and NEXPTIME-completeness of DEL-sequents
- The complexity of model-checking tail-recursive higher-order fixpoint logic
- Reasoning about XML constraints based on XML-to-relational mappings
- Finite-word hyperlanguages
- Decidability and complexity of action-based temporal planning over dense time
- Consensus game acceptors and iterated transductions
- LTL over integer periodicity constraints
- On Composing Finite Forests with Modal Logics
- Turing machines for dummies. Why representations do matter
- Extended bounded response LTL: a new safety fragment for efficient reactive synthesis
- Extending inclusion dependencies with conditions
- Complexity of question/answer games
- scientific article; zbMATH DE number 1386183 (Why is no real title available?)
- 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)
