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

Formal System Analysis

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

28 Citations (Scopus)

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.

Original language	English
Pages (from-to)	6-1/28
Journal	Journal of the ACM
Volume	54
Issue number	2
DOIs	https://doi.org/10.1145/1219092.1219094
Publication status	Published - 2007

Access to Document

10.1145/1219092.1219094

Cite this

@article{46f53b062f384010b4194bdd8df5f8ac,

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.",

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

year = "2007",

doi = "10.1145/1219092.1219094",

language = "English",

volume = "54",

pages = "6--1/28",

journal = "Journal of the ACM",

issn = "0004-5411",

publisher = "Association for Computing Machinery, Inc.",

number = "2",

}

TY - JOUR

T1 - A characterization of regular expressions under bisimulation

AU - Baeten, J.C.M.

AU - Corradini, F.

AU - Grabmayer, C.A.

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.

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.

U2 - 10.1145/1219092.1219094

DO - 10.1145/1219092.1219094

M3 - Article

SN - 0004-5411

VL - 54

SP - 6-1/28

JO - Journal of the ACM

JF - Journal of the ACM

IS - 2

ER -

A characterization of regular expressions under bisimulation

Abstract

Access to Document

Fingerprint

Cite this