Recurring Dominoes: Making the Highly Undecidable Highly Understandable
DOI10.1016/S0304-0208(08)73075-5zbMATH Open0531.68003OpenAlexW1501571921MaRDI QIDQ3313255FDOQ3313255
Authors: David Harel 
Publication date: 1985
Published in: Topics in the Theory of Computation, Selected Papers of the International Conference on ‘Foundations of Computation Theory’, FCT '83 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-0208(08)73075-5
Recommendations
- 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
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) Complexity of computation (including implicit computational complexity) (03D15) Undecidability and degrees of sets of sentences (03D35)
Cited In (32)
- Subshifts, Languages and Logic
- More on looping vs. repeating in dynamic logic
- Logic and Game Theory
- Augmenting ATL with strategy contexts
- From logic to tiling
- A codicity undecidable problem in the plane.
- Rabin's theorem in the concurrency setting: a conjecture
- Complexity analysis of propositional concurrent programs using domino tiling
- Temporal Logic with Recursion.
- Communication in concurrent dynamic logic
- The complexity of propositional linear temporal logics in simple cases
- On axiomatizations of public announcement logic
- Polyadic dynamic logics for HPSG parsing
- On the solvability of domino snake problems
- Past is for free: on the complexity of verifying linear temporal properties with past
- A modal logic for supervised learning
- The dark side of interval temporal logic: marking the undecidability border
- On undecidability of propositional temporal logics on trace systems
- Models and logics for true concurrency.
- Undecidability results on two-variable logics
- INTERLEAVING LOGIC AND COUNTING
- Satisfiability of Arbitrary Public Announcement Logic with Common Knowledge is Σ^1_1-hard
- An essay in combinatory dynamic logic
- Temporal logic with recursion
- Model checking propositional dynamic logic with all extras
- Title not available (Why is that?)
- A multiparameter analysis of domino tiling with an application to concurrent systems
- The decision problems about the periodic solutions of the domino problems
- Process logic with regular formulas
- Bisimulation-invariant PTIME and higher-dimensional \(\mu\)-calculus
- Changing a Semantics: Opportunism or Courage?
- Subshifts as models for MSO logic
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)
