Deterministic asynchronous automata for infinite traces (Q1338892)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Deterministic asynchronous automata for infinite traces
scientific article

    Statements

    Deterministic asynchronous automata for infinite traces (English)
    0 references
    0 references
    0 references
    23 November 1994
    0 references
    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.
    0 references
    infinite traces
    0 references
    non-terminating concurrent systems
    0 references
    Muller automaton
    0 references

    Identifiers