Classifying recognizable infinitary trace languages using word automata

We address the problem of providing a Borel-like classification of languages of infinite Mazurkiewicz traces, and provide a solution in the framework of ω-automata over infinite words – which is invoked via the sets of linearizations of infinitary trace languages. We identify trace languages whose linearizations are recognized by deterministic weak or deterministic Büchi (word) automata. We present a characterization of the class of linearizations of all recognizable ω-trace languages in terms of Muller (word) automata. Finally, we show that the linearization of any recognizable ω-trace language can be expressed as a Boolean combination of languages recognized by our class of deterministic Büchi automata.

Authors

• Namit Chaturvedi
• Marcus Gelderie

Keywords

• Mazurkiewicz traces
• Omega-regular languages
• Classification
• Finite state automata