Multiple-person alternation
- 1 October 1979
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 348-363
- https://doi.org/10.1109/sfcs.1979.25
Abstract
We generalize the alternation machines of Chandra, Kozen and Stockmeyer [1] and the private alternation machines of Reif [14] to model multiple person (team) games of incomplete information. The resulting classes of machines are "multiple person alternation machines". The characterization of certain time and space bounded versions of these machines demonstrate interesting relationships between ordinary time and space hierarchies (Table 1). Our results are applied to relative succintness and power questions of finite state machines and to complexity questions of parallel finite state machines. Other machine variants, including private alternating pushdown store automata and Markovian alternation machines, are discussed.Keywords
This publication has 11 references indexed in Scilit:
- Universal games of incomplete informationPublished by Association for Computing Machinery (ACM) ,1979
- GO is pspace hardPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1978
- On alternationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1978
- Alternating pushdown automataPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1978
- Game interpretation of the deadlock avoidance problemCommunications of the ACM, 1977
- AlternationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1976
- On the complexity of the theories of weak direct products (Preliminary Report)Published by Association for Computing Machinery (ACM) ,1974
- Word problems requiring exponential time(Preliminary Report)Published by Association for Computing Machinery (ACM) ,1973
- The equivalence problem for regular expressions with squaring requires exponential spacePublished by Institute of Electrical and Electronics Engineers (IEEE) ,1972
- Relationships between nondeterministic and deterministic tape complexitiesJournal of Computer and System Sciences, 1970