A characterization of regular expressions under bisimulation
J. C. M. Baeten, Flavio Corradini, Clemens Grabmayer · Journal of the ACM · 2007
We solve an open question of Milner [1984]. We define a set of so-called well-behaved finite automata that, modulo bisimulation equivalence, corresponds exactly to the set of regular expressions, and we show how to determine whether a given finite automaton is in this set. As an application, we consider the star height problem.