A characterization of regular expressions under bisimulation

J.C.M. Baeten; F. Corradini; C.A. Grabmayer

doi:10.1145/1219092.1219094

A characterization of regular expressions under bisimulation

J.C.M. Baeten, F. Corradini, C.A. Grabmayer

Research output: Contribution to Journal › Article › Academic › peer-review

Abstract

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. © 2007 ACM.

Original language	English
Journal	Journal of the Association for Computing Machinery
Volume	54
Issue number	2
DOIs	https://doi.org/10.1145/1219092.1219094
Publication status	Published - 2007

Bibliographical note

DBLP:journals/jacm/BaetenCG07

Access to Document

10.1145/1219092.1219094

Persistent URL (handle)

Copy link address

Cite this

@article{38b24dab203b42739c546dc20d601ff9,

title = "A characterization of regular expressions under bisimulation",

abstract = "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. {\textcopyright} 2007 ACM.",

author = "J.C.M. Baeten and F. Corradini and C.A. Grabmayer",

note = "DBLP:journals/jacm/BaetenCG07 ",

year = "2007",

doi = "10.1145/1219092.1219094",

language = "English",

volume = "54",

journal = "Journal of the Association for Computing Machinery",

issn = "0004-5411",

publisher = "Association for Computing Machinery (ACM)",

number = "2",

}

TY - JOUR

T1 - A characterization of regular expressions under bisimulation

AU - Baeten, J.C.M.

AU - Corradini, F.

AU - Grabmayer, C.A.

N1 - DBLP:journals/jacm/BaetenCG07

PY - 2007

Y1 - 2007

N2 - 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. © 2007 ACM.

AB - 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. © 2007 ACM.

U2 - 10.1145/1219092.1219094

DO - 10.1145/1219092.1219094

M3 - Article

SN - 0004-5411

VL - 54

JO - Journal of the Association for Computing Machinery

JF - Journal of the Association for Computing Machinery

IS - 2

ER -

A characterization of regular expressions under bisimulation

Abstract

Bibliographical note

Access to Document

Persistent URL (handle)

Fingerprint

Cite this