Domino-tiling games

DOI10.1016/0022-0000(86)90036-XzbMath0618.68045OpenAlexW2030473999MaRDI QIDQ1822501

Bogdan S. Chlebus

Publication date: 1986

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(86)90036-x

zbMATH Keywords

tilingcomplexity hierarchypropositional program logicsDomino Problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 2-person games (91A05) Applications of game theory (91A80) Logic in computer science (03B70) Combinatorial aspects of tessellation and tiling problems (05B45)

Related Items (28)

Turing Machines for Dummies ⋮ Consensus Game Acceptors ⋮ On the Hybrid Extension of CTL and CTL + ⋮ Centralized asynchronous broadcast in radio networks ⋮ Games for active XML revisited ⋮ Common knowledge and update in finite environments ⋮ The intersection problem for finite monoids ⋮ Extending inclusion dependencies with conditions ⋮ Conjunctive query containment over trees using schema information ⋮ Typechecking top-down XML transformations: Fixed input or output schemas ⋮ Consensus Game Acceptors and Iterated Transductions ⋮ Polyomino tilings, cellular automata and codicity ⋮ A multiparameter analysis of domino tiling with an application to concurrent systems ⋮ Unnamed Item ⋮ Modulo constraints and the complexity of typechecking XML views ⋮ Playing Savitch and Cooking Games ⋮ Multi-buffer simulations: decidability and complexity ⋮ Turing machines with access to history ⋮ Complexity of the universal theory of modal algebras ⋮ On timeline-based games and their complexity ⋮ On the Complexity of Branching-Time Logics ⋮ Complexity of the universal theory of bounded residuated distributive lattice-ordered groupoids ⋮ Unnamed Item ⋮ The complexity of hybrid logics over equivalence relations ⋮ Branching-time logics repeatedly referring to states ⋮ Complexity analysis of propositional concurrent programs using domino tiling ⋮ Simple sentences that are hard to decide ⋮ Query automata over finite trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing a perfect strategy for nxn chess requires time exponential in n
• On the computational complexity of satisfiability in propositional logics of programs
• Space-bounded reducibility among combinatorial problems
• Relating refined space complexity classes
• The polynomial-time hierarchy
• Propositional dynamic logic of regular programs
• Relationships between nondeterministic and deterministic tape complexities
• ENTSCHEIDUNGSPROBLEM REDUCED TO THE AEA CASE
• Provably Difficult Combinatorial Games
• Alternation
• The Computational Complexity of Provability in Systems of Modal Propositional Logic
• Two-Tape Simulation of Multitape Turing Machines
• The undecidability of the domino problem

This page was built for publication: Domino-tiling games