Recurring Dominoes: Making the Highly Undecidable Highly Understandable
Complexity of computation (including implicit computational complexity) (03D15) Undecidability and degrees of sets of sentences (03D35) Combinatorial aspects of tessellation and tiling problems (05B45) Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17) Abstract data types; algebraic specification (68Q65)
In recent years many diverse logical systems for reasoning about programs have been shown to possess a highly undecidable, viz \(\Pi_ 1^ 1\)- complete, validity problem. All such known results are reproved in this paper in a uniform and transparent manner by reductions from recurring domino problems. These are simple variants of the classical unbounded domino (or tiling) problems introduced by Wang and the bounded versions defined by Lewis. While the former are (weakly) undecidable and the latter complete in various complexity classes, the problems in the new class are \(\Sigma^ 1_ 1\)-complete. It is hoped that the paper, which contains also NP-, PSPACE-, \(\Pi^ 0_ 1-\) and \(\Pi^ 0_ 2-hardness\) results for logical systems, will enhance interest in the appealing medium of domino problems as a useful set of reduction tools for exhibiting bad behavior. For the entire collection see [Zbl 0546.00030].
- scientific article; zbMATH DE number 3843130
- The undecidability of the domino problem
- Highly Undecidable Problems about Recognizability by Tiling Systems
- Two-by-Two Substitution Systems and the Undecidability of the Domino Problem
- Undecidability of domino games and hhp-bisimilarity.
- scientific article; zbMATH DE number 3976339
- scientific article; zbMATH DE number 3876591
- scientific article; zbMATH DE number 4057497
- Logical undecidabilities made easy
- Polyadic dynamic logics for HPSG parsing
- Process logic with regular formulas
- Communication in concurrent dynamic logic
- A multiparameter analysis of domino tiling with an application to concurrent systems
- On undecidability of propositional temporal logics on trace systems
- On the solvability of domino snake problems
- A codicity undecidable problem in the plane.
- From logic to tiling
- The complexity of propositional linear temporal logics in simple cases
- Bisimulation-invariant PTIME and higher-dimensional \(\mu\)-calculus
- Temporal logic with recursion
- A modal logic for supervised learning
- The dark side of interval temporal logic: marking the undecidability border
- Rabin's theorem in the concurrency setting: a conjecture
- More on looping vs. repeating in dynamic logic
- Model checking propositional dynamic logic with all extras
- Past is for free: on the complexity of verifying linear temporal properties with past
- Complexity analysis of propositional concurrent programs using domino tiling
- Changing a Semantics: Opportunism or Courage?
- Subshifts, Languages and Logic
- scientific article; zbMATH DE number 3976339 (Why is no real title available?)
- Subshifts as models for MSO logic
- On axiomatizations of public announcement logic
- Undecidability results on two-variable logics
- Logic and Game Theory
- Models and logics for true concurrency.
- Temporal Logic with Recursion.
- INTERLEAVING LOGIC AND COUNTING
- Satisfiability of Arbitrary Public Announcement Logic with Common Knowledge is Σ^1_1-hard
- FO logic on cellular automata orbits equals MSO logic
- Contributions to the domino problem: seeding, recurrence and satisfiability
- HyperLTL satisfiability is highly undecidable, \(\mathrm{HyperCTL}^*\) is even harder
- Computational characterization of surface entropies for \(\mathbb{Z}^2\) subshifts of finite type
- On homogeneous models of fluted languages
- The complexity of second-order HyperLTL
- The decision problems about the periodic solutions of the domino problems
- An essay in combinatory dynamic logic
- Augmenting ATL with strategy contexts
This page was built for publication: Recurring Dominoes: Making the Highly Undecidable Highly Understandable
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3313255)