Journal Article

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 Authors

Cited Authors

  • Peterson, GL; Reif, JH

Published Date

  • January 1, 1979

Published In

Start / End Page

  • 348 - 363

International Standard Serial Number (ISSN)

  • 0272-5428

Citation Source

  • Scopus