\(X\)-automata on \(\omega\)-words (Q1210539)

Five criteria for accepting infinite words were proposed by \textit{L. H. Landweber} [Math. Systems Theory 3, 376-384 (1969; Zbl 0182.02402)]. The relative power of these five criteria have then been compared e.g. for finite-state automata, pushdown automata, Turing machines, and Petri nets. The results show that the acceptance types have the same relative power independently of the storage used by the automaton involved. The paper investigates, using a general framework, the similarities between the results obtained for the various specific types of automata. The abstract model of storage used is called a storage type. It describes the storage configurations, together with the tests and transformations that can be applied to them. Automata equipped with a specific storage \(X\) are called \(X\) automata. Six families of \(\omega\)-languages that can be accepted by an \(X\) automaton using six different acceptance criteria on the sequence of states entered by the automaton during a computation are studied. The main tool is a characterisation of the \(\omega\)- languages accepted by \({\mathcal X}\) automata in terms of infinitary transductions applied to the \(\omega\)-languages accepted by finite-state automata. The inclusion results between the six families for \(X\)-automata are similar to those formed by the families for finite-state automata. It is also shown that the topological upper bounds as given by \textit{Landweber} for deterministic finite-state automata can be generalized for \(X\) automata. This implies that for deterministic and real-time \(X\) automata the inclusions are strict.