Solitaire automata

DOI10.1016/0022-0000(85)90007-8MaRDI QIDQ1058475zbMATH OpenOpenAlexFDO

Authors Richard E. Ladner, Jeffrey K. Norman

Publication date 1985

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(85)90007-8

zbMATH Keywords

imperfect informationsolitaire automatonsolitaire gamesspace and time boundsTuring machines

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Formal languages and automata (68Q45) Learning and adaptive systems in artificial intelligence (68T05) Game theory (91A99)

Review text

The notion of a solitaire automaton is introduced to model the class of solitaire games. Space and time bounded solitaire automata with varying degrees of information are investigated. In general, solitaire automata have partial or imperfect information. The principal results are (i) s(n)-space bounded solitaire automata are equivalent to Turing machines which run in space exponential in s(n) and (ii) t(n)-time bounded solitaire automata are equivalent to alternating Turing machines which run in time t(n). The power of solitaire automata is also determined when the information is perfect or zero.

Recommendations

• scientific article; zbMATH DE number 8789
• The complexity of solitaire
• The Complexity of Solitaire
• Probabilistic game automata
• Publication:4720789

Cites work

• Alternation
• Provably Difficult Combinatorial Games
• The complexity of two-player games of incomplete information
• The NP-completeness column: An ongoing guide

Cited in

(9)

• The complexity of solitaire
• Decision algorithms for multiplayer noncooperative games of incomplete information
• Probabilistic game automata
• scientific article; zbMATH DE number 5925087 (Why is no real title available?)
• The Complexity of Solitaire
• Classifying the computational complexity of problems
• scientific article; zbMATH DE number 8789 (Why is no real title available?)
• Triangle solitaire
• Turing machines with access to history

This page was built for publication: Solitaire automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1058475)