scientific article; zbMATH DE number 1048047
From MaRDI portal
Publication:4348133
combinatorial reductionscomplexity classesdeterministic exponential time lowerboundencoding machine computationshardness of combinatorial problemsHilbert 10 reductionmaster reductionsreduction chain to the knapsack problemsatisfiability in propositional dynamic logictiling
Decidability of theories and sets of sentences (03B25) Turing machines and related notions (03D10) Complexity of computation (including implicit computational complexity) (03D15) Combinatorial aspects of tessellation and tiling problems (05B45) Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05)
Recommendations
Cited in
(61)- Frontier between decidability and undecidability: A survey
- A strip-like tiling algorithm
- Decidability and complexity of the fragments of the modal logic of Allen's relations over the rationals
- On relative and probabilistic finite counterability
- Multi-buffer simulations: decidability and complexity
- Tilings: recursivity and regularity
- The monodic fragment of propositional term modal logic
- From decidability to undecidability by considering regular sets of instances
- Logical separability of labeled data examples under ontologies
- Decidability and complexity of action-based temporal planning over dense time
- Capacitated automata and systems
- Model checking for hybrid branching-time logics
- On timeline-based games and their complexity
- Query inseparability for \(\mathcal{ALC}\) ontologies
- Reasoning about XML constraints based on XML-to-relational mappings
- Complexity of question/answer games
- LTL over integer periodicity constraints
- Decidable subsets of open logic and an algorithm for R-calculus
- Which XML schemas are streaming bounded repairable?
- Tableau method and NEXPTIME-completeness of DEL-sequents
- Undecidability of multi-modal hybrid logics
- Turing machines for dummies. Why representations do matter
- A logical approach to locality in pictures languages
- Fast domino tileability
- Complexity analysis of propositional concurrent programs using domino tiling
- Martin Davis and Hilbert's tenth problem
- Satisfiability for SCULPT-schemas for CSV-like data
- Consensus game acceptors
- Branching-time logics with path relativisation
- Extending inclusion dependencies with conditions
- On simplification of schema mappings
- Bounded repairability of word languages
- Consensus game acceptors and iterated transductions
- Computational aspects of M. C. Escher's ribbon patterns
- scientific article; zbMATH DE number 1386183 (Why is no real title available?)
- The complexity of model-checking tail-recursive higher-order fixpoint logic
- scientific article; zbMATH DE number 7577569 (Why is no real title available?)
- scientific article; zbMATH DE number 3894472 (Why is no real title available?)
- Playing Savitch and cooking games
- On the decidability of elementary modal logics
- Infinite games with finite knowledge gaps
- On Composing Finite Forests with Modal Logics
- Closest substring problems for regular languages
- On the decidability of finding a positive ILP-instance in a regular set of ILP-instances
- The tail-recursive fragment of timed recursive CTL
- Are bundles good deals for first-order modal logic?
- Finite-word hyperlanguages
- First-order temporal logic on finite traces: semantic properties, decidable fragments, and applications
- 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
- Deciding the existence of interpolants and definitions in first-order modal logic
- Homogeneity and homogenizability: hard problems for the logic SNP
- Contributions to the domino problem: seeding, recurrence and satisfiability
- A quantitative extension of interval temporal logic over infinite words
- Rewriting of regular expressions and regular path queries
- The complexity of pure maxmin strategies in two-player extensive-form games
- Finding small proofs for description logic entailments: theory and practice
- On the complexity of the conditional independence implication problem with bounded cardinalities
- On the freeze quantifier in Constraint LTL: Decidability and complexity
- On keys and functional dependencies as first-class citizens in description logics
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)
