Skip to main content

MULTIPLE-PERSON ALTERNATION.

Publication ,  Journal Article
Peterson, GL; Reif, JH
Published in: Annual Symposium on Foundations of Computer Science - Proceedings
January 1, 1979

The alternation machines of A. K. Chandra et al. , and the private alternation machines of J. H. Reif are generalized 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 demonstrates interesting relationships between ordinary time and space hierarchies. The 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

Published In

Annual Symposium on Foundations of Computer Science - Proceedings

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. Annual Symposium on Foundations of Computer Science - Proceedings, 348–363.
Peterson, G. L., and J. H. Reif. “MULTIPLE-PERSON ALTERNATION.Annual Symposium on Foundations of Computer Science - Proceedings, January 1, 1979, 348–63.
Peterson GL, Reif JH. MULTIPLE-PERSON ALTERNATION. Annual Symposium on Foundations of Computer Science - Proceedings. 1979 Jan 1;348–63.
Peterson, G. L., and J. H. Reif. “MULTIPLE-PERSON ALTERNATION.Annual Symposium on Foundations of Computer Science - Proceedings, Jan. 1979, pp. 348–63.
Peterson GL, Reif JH. MULTIPLE-PERSON ALTERNATION. Annual Symposium on Foundations of Computer Science - Proceedings. 1979 Jan 1;348–363.

Published In

Annual Symposium on Foundations of Computer Science - Proceedings

ISSN

0272-5428

Publication Date

January 1, 1979

Start / End Page

348 / 363