A characterization of regular expressions under bisimulation

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 cons...

Full description

Saved in:
Bibliographic Details
Published in:Journal of the ACM 2007-04, Vol.54 (2), p.6-6
Main Authors: Baeten, J. C. M., Corradini, F., Grabmayer, C. A.
Format: Article
Language:English
Subjects:
Equivalence
Mathematical analysis
Stars
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0004-5411
1557-735X
DOI:10.1145/1219092.1219094