Solitaire automata (Q1058475): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
| Property / cites work | |||
| Property / cites work: Alternation / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: The NP-completeness column: An ongoing guide / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: The complexity of two-player games of incomplete information / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Provably Difficult Combinatorial Games / rank | |||
Normal rank | |||
Latest revision as of 16:45, 14 June 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Solitaire automata |
scientific article |
Statements
Solitaire automata (English)
0 references
1985
0 references
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.
0 references
space and time bounds
0 references
solitaire automaton
0 references
solitaire games
0 references
imperfect information
0 references
Turing machines
0 references
