Domino-tiling games (Q1822501): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q794424 |
Changed an Item |
||
| Property / reviewed by | |||
| Property / reviewed by: Antoni Kreczmar / rank | |||
Normal rank | |||
Revision as of 23:19, 20 February 2024
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
