Multiple-Person Alternation

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.

Authors

• Gary L. Peterson
• John H. Reif

Keywords

• Automata
• Concrete
• Game theory
• Law
• Legal factors
• History
• Computer science
• Computational modeling
• Upper bound
• Information analysis
• Time And Space
• Team Sports
• Antisocial Personality Disorder
• Multiple Machine
• Time Complexity
• Local State
• Gameplay
• Current Information
• Space Complexity
• State Machine
• Blindfolded
• Perfect Information
• Logic Of Theory
• Team Size
• Player Position
• Truth Table
• Sequence Of Configurations
• Stage Of The Game
• Multiple Games
• Regular Language