Recurring Dominoes: Making the Highly Undecidable Highly Understandable

From MaRDI portal





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].




Cited in
(38)








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)