Recurring Dominoes: Making the Highly Undecidable Highly Understandable

DOI10.1016/S0304-0208(08)73075-5zbMath0531.68003OpenAlexW1501571921MaRDI QIDQ3313255

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

zbMATH Keywords

undecidabilityprogram logictiling problemrecurring domino problems

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Abstract data types; algebraic specification (68Q65) Complexity of computation (including implicit computational complexity) (03D15) Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17) Combinatorial aspects of tessellation and tiling problems (05B45)

Related Items (30)

On the solvability of domino snake problems ⋮ Communication in concurrent dynamic logic ⋮ Changing a Semantics: Opportunism or Courage? ⋮ A modal logic for supervised learning ⋮ Subshifts as models for MSO logic ⋮ Augmenting ATL with strategy contexts ⋮ A codicity undecidable problem in the plane. ⋮ INTERLEAVING LOGIC AND COUNTING ⋮ Satisfiability of Arbitrary Public Announcement Logic with Common Knowledge is Σ^1_1-hard ⋮ Bisimulation-invariant PTIME and higher-dimensional \(\mu\)-calculus ⋮ On axiomatizations of public announcement logic ⋮ A multiparameter analysis of domino tiling with an application to concurrent systems ⋮ Temporal Logic with Recursion. ⋮ On undecidability of propositional temporal logics on trace systems ⋮ 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 ⋮ Undecidability results on two-variable logics ⋮ Models and logics for true concurrency. ⋮ Temporal logic with recursion ⋮ Polyadic dynamic logics for HPSG parsing ⋮ Subshifts, Languages and Logic ⋮ Past is for Free: on the Complexity of Verifying Linear Temporal Properties with Past ⋮ Logic and Game Theory ⋮ The complexity of propositional linear temporal logics in simple cases ⋮ Process logic with regular formulas ⋮ Complexity analysis of propositional concurrent programs using domino tiling ⋮ From logic to tiling ⋮ An essay in combinatory dynamic logic

This page was built for publication: Recurring Dominoes: Making the Highly Undecidable Highly Understandable