Multiple-person alternation
Publication
, Conference
Peterson, GL; Reif, JH
Published in: Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
January 1, 1979
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.
Duke Scholars
Altmetric Attention Stats
Dimensions Citation Stats
Published In
Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
DOI
ISSN
0272-5428
Publication Date
January 1, 1979
Start / End Page
348 / 363
Citation
APA
Chicago
ICMJE
MLA
NLM
Peterson, G. L., & Reif, J. H. (1979). Multiple-person alternation. In Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS (pp. 348–363). https://doi.org/10.1109/SFCS.1979.25
Peterson, G. L., and J. H. Reif. “Multiple-person alternation.” In Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, 348–63, 1979. https://doi.org/10.1109/SFCS.1979.25.
Peterson GL, Reif JH. Multiple-person alternation. In: Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS. 1979. p. 348–63.
Peterson, G. L., and J. H. Reif. “Multiple-person alternation.” Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, 1979, pp. 348–63. Scopus, doi:10.1109/SFCS.1979.25.
Peterson GL, Reif JH. Multiple-person alternation. Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS. 1979. p. 348–363.
Published In
Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
DOI
ISSN
0272-5428
Publication Date
January 1, 1979
Start / End Page
348 / 363