Theories of automata on ω-tapes: A simplified approach

摘要

Using a combinatorial lemma on regular sets, and a technique of attaching a control unit to a parallel battery of finite automata, a simple and transparent development of McNaughton's theory of automata on ω-tapes is given. The lemma and the technique are then used to give an independent and equally simple development of Büchi's theory of nondeterministic automata on these tapes. Some variants of these models are also studied. Finally a third independent approach, modelled after a simplified version of Rabin's theory of automata on infinite trees, is developed.