Domino-tiling games

Bogdan S. Chlebus(corresponding author)

*Corresponding author for this work

University of Warsaw

Scholary Output:

Contribution to journal

Article

Peer-review

Open access

Abstract

Games in which players build domino tilings are considered. The computational complexity of problems of existence of winning strategies is investigated. These problems are shown to be complete in the respective complexity classes, e.g., SQUARE TILING GAME is complete in PSPACE, HIGH TILING GAME is complete in 2EXPTIME and has a doubly exponential time lower bound. As an application, new simple hardness proofs for certain propositional logics are obtained.

Publication Information

Output type

Scholary Output:

Contribution to journal

Article

Peer-review

Original language

English (US)

Pages from-to (Number of pages)

Pages 374-392 (19 pages)

Journal (Volume, Issue Number)

Journal of Computer and System Sciences (Volume 32, Issue 3)

Publication milestones

Published - 06/1986

Publication status

Published - 06/1986

ISSN

0022-0000

Publication IDs

Scopus: 0022739258

Access to documents

10.1016/0022-0000(86)90036-X

Publication metrics

Metrics

Fractional count

Scopus

citations

PlumX, opens in new tab

Citation count

Captures