Domino-tiling games (Q1822501)

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.