X-automata on -words

DOI10.1016/0304-3975(93)90349-XMaRDI QIDQ1210539zbMATH OpenOpenAlexFDO

Authors Joost Engelfriet, Hendrik Jan Hoogeboom

Publication date 30 August 1993

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(93)90349-x

zbMATH Keywords

\(\omega\)-languages \(\omega\)-words finite-state automata real-time automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Review text

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.

Recommendations

Cites work

Cited in

(24)

This page was built for publication: \(X\)-automata on \(\omega\)-words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1210539)