Solitaire automata
type: Item
instance of: scholarly article
title: Solitaire automata
zbMATH Open document ID: 0564.90108
DOI: 10.1016/0022-0000(85)90007-8
author: Richard E. Ladner
author: Jeffrey K. Norman
published in: Journal of Computer and System Sciences
publication date: 1985-01-01T00:00:00Z
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.
Mathematics Subject Classification ID: 91A99
Mathematics Subject Classification ID: 03D10
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68T05
zbMATH DE Number: 3900565
zbMATH Keywords: space and time bounds
zbMATH Keywords: solitaire automaton
zbMATH Keywords: solitaire games
zbMATH Keywords: imperfect information
zbMATH Keywords: Turing machines
MaRDI profile type: Publication
full work available at URL: 0022-0000(85)90007-8
OpenAlex ID: W4210422112
cites work: Alternation
cites work: The NP-completeness column: An ongoing guide
cites work: The complexity of two-player games of incomplete information
cites work: Provably Difficult Combinatorial Games
description: scientific article; zbMATH DE number 3900565