Presentation Namit Chaturvedi: Languages of Infinite Traces and Deterministic Asynchronous Automata

Abstract:

In the theory of deterministic automata for languages of infinite words, a fundamental result relates the family of infinitary limits of regular languages and the family of omega-languages recognized by deterministic Buechi automata. Furthermore, a theorem due to L. Landweber states that an omega-regular language is recognized by a deterministic Buechi automaton if and only if it is recognized by a deterministic Muller automaton whose acceptance component is closed under supersets. With the known definitions of asynchronous automata, these results does not extend to the context of traces. We introduce the family of deterministic, synchronization-aware asynchronous automata which allows us to establish these results, while the definition of Muller automata obtained therein captures all omega-regular trace languages. We also positively answer an open question in the theory of traces, namely, whether every omega-regular trace language can be expressed as a finite Boolean combination of deterministically Buechi recognizable languages.

Bookmark the permalink.