Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456

Address: [go: Go Back, main page]
Remove Scripts Accept Cookies Show Images Show Referer Rotate13 Base64 Strip Meta Strip Title Session Cookies

Baeten and Corradini Solve a Long-standing Problem of Milner's

18 March 2005

One of the classic papers in process theory is Milner's "A complete inference system for a class of regular behaviours", JCSS 28(3), 1984. There, Milner gave a complete axiomatization of strong bisimulation equivalence over the regular fragment of CCS. He also studied regular expressions modulo strong bisimularity, offered a sound inference system for this congruence over regular expressions, and realized that, in the setting of process theory, the language of regular expressions is less expressive than the regular fragment of CCS/mu-expressions.

In the aforementioned seminal paper, Milner raised two open problems:

1. To characterize the collection of finite labelled transition systems/mu-expressions that can be denoted by regular expressions modulo strong bisimilarity, and
2. To prove the completeness of his proposed axiomatization of strong bisimilarity over the language of regular expressions.

The two problems are somewhat related as a solution to the former is likely to play an important role in tackling the second.

Despite intensive work in the process theory community peaking in partial solutions to the above problems by Bosscher, Corradini, De Nicola/Labella and Fokkink, both of the above problems have been open since 1984.

We are now lucky to have the paper "A Characterization of Regular Expressions in Process Algebra" by Jos Baeten and Flavio Corradini that presents a solution to the former in terms of a structural property that characterizes the set of finite automata that can be denoted by regular expressions modulo strong bisimilarity. This is a non-trivial, and, to my mind, important achievement in process theory. I congratulate the authors for having their paper accepted at LICS 2005.

Well done Flavio and Jos, but now make your paper available on line!