Domino-tiling games (Q1822501)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Domino-tiling games |
scientific article |
Statements
Domino-tiling games (English)
0 references
1986
0 references
The paper presents the application of the Domino Problem into the complexity hierarchy. It is well known that some infinite planar cases of the Domino Problem are unsolvable. When the game is restricted, we can obtain some complexity classes. Namely, the Square Tiling Domino Problem is complete in PSpace, while the Rectangle Tiling Domino Problem is complete in ExpTime. For some more complicated restrictions the author found a tiling problem complete in ExpSpace and another complete in 2ExpTime. The paper ends with some variants of propositional program logics and their complexities are characterized.
0 references
complexity hierarchy
0 references
Domino Problem
0 references
tiling
0 references
propositional program logics
0 references
