Deterministic asynchronous automata for infinite traces

DOI10.1007/BF01178512MaRDI QIDQ1338892zbMATH OpenFDO

Authors Volker Diekert, Anca Muscholl

Publication date 23 November 1994

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01178512

zbMATH Keywords

infinite traces Muller automaton non-terminating concurrent systems

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70)

Review text

Infinite traces form a suitable framework for describing non-terminating concurrent systems. Especially interesting are systems which may be observed using finite state devices. From the automata-theoretic viewpoint we are interested in automata with distributed control, more precisely in asynchronous cellular automata. The main result of the present paper provides a positive answer to the main open question in this field and extends McNaughton's Theorem from \(\omega\)-word languages to recognizable real trace languages. Concretely, we show the equivalence between the family of recognizable real trace languages and the family of real trace languages which can be accepted by deterministic asynchronous cellular Muller automata. As a special case we obtain that every closed (w.r.t. the independence relation \(I)\) \(\omega\)-word language is accepted by some \(I\)-diamond deterministic Muller automaton.

Recommendations

Cites work

Cited in

(14)

This page was built for publication: Deterministic asynchronous automata for infinite traces

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