Transition-based vs. state-based acceptance for automata over infinite words

Abstract: In the context of automata over infinite words, acceptance is traditionally defined in terms of the states visited infinitely often during a run. However, there is a growing trend towards defining acceptance based on transitions rather than states.

In this talk, I will survey a number of results showing the striking differences between the two models, and provide arguments in favour of using transitions as the standard acceptance method. Along the way, we will revisit key historical results that have shaped the theory of automata over infinite words.

formal languages and automata theory

Audience: researchers in the topic

( slides | video )

One FLAT World Seminar