Solitaire automata

摘要

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.