Solitaire automata (Q1058475)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3900565
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Solitaire automata |
scientific article; zbMATH DE number 3900565 |
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
0.7523208260536194
0 references
0.743345320224762
0 references
0.7401020526885986
0 references
