{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:53:00Z","timestamp":1750308780252,"version":"3.41.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2007,4,1]],"date-time":"2007-04-01T00:00:00Z","timestamp":1175385600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2007,4]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/1219092.1219094","type":"journal-article","created":{"date-parts":[[2007,6,6]],"date-time":"2007-06-06T14:37:11Z","timestamp":1181140631000},"page":"6","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":20,"title":["A characterization of regular expressions under bisimulation"],"prefix":"10.1145","volume":"54","author":[{"given":"J. C. M.","family":"Baeten","sequence":"first","affiliation":[{"name":"Technische Universiteit Eindhoven, Eindhoven, The Netherlands"}]},{"given":"F.","family":"Corradini","sequence":"additional","affiliation":[{"name":"Universit\u00e0 di Camerino, Camerino, Italy"}]},{"given":"C. A.","family":"Grabmayer","sequence":"additional","affiliation":[{"name":"Vrije Universiteit, Amsterdam, The Netherlands"}]}],"member":"320","published-online":{"date-parts":[[2007,4]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Aceto L. Fokkink W. and Verhoef C. 2001. Structural operational semantics. In Handbook of Process Algebra J. Bergstra A. Ponse and S. Smolka Eds. Elsevier Science Amsterdam The Netherlands 197--292.  Aceto L. Fokkink W. and Verhoef C. 2001. Structural operational semantics. In Handbook of Process Algebra J. Bergstra A. Ponse and S. Smolka Eds. Elsevier Science Amsterdam The Netherlands 197--292.","key":"e_1_2_2_1_1","DOI":"10.1016\/B978-044482830-9\/50021-7"},{"doi-asserted-by":"publisher","key":"e_1_2_2_2_1","DOI":"10.1016\/0890-5401(88)90027-2"},{"key":"e_1_2_2_3_1","volume-title":"Proceedings CONCUR'90","volume":"458","author":"Baeten J.","unstructured":"Baeten , J. , and Bergstra , J . 1990. Process algebra with a zero object . In Proceedings CONCUR'90 , J. Baeten and J. Klop, Eds. Lecture Notes in Computer Science , vol. 458 . Springer-Verlag, New York, 83--98. Baeten, J., and Bergstra, J. 1990. Process algebra with a zero object. In Proceedings CONCUR'90, J. Baeten and J. Klop, Eds. Lecture Notes in Computer Science, vol. 458. Springer-Verlag, New York, 83--98."},{"doi-asserted-by":"publisher","key":"e_1_2_2_4_1","DOI":"10.1016\/0304-3975(87)90052-1"},{"doi-asserted-by":"publisher","key":"e_1_2_2_5_1","DOI":"10.1145\/174130.174141"},{"doi-asserted-by":"publisher","key":"e_1_2_2_6_1","DOI":"10.1109\/LICS.2005.43"},{"unstructured":"Baeten J. and Verhoef C. 1995. Concrete process algebra. In Handbook of Logic in Computer Science S. Abramsky D. Gabbay and T. Maibaum Eds. Vol. 4. Oxford University Press Oxford UK 149--269.   Baeten J. and Verhoef C. 1995. Concrete process algebra. In Handbook of Logic in Computer Science S. Abramsky D. Gabbay and T. Maibaum Eds. Vol. 4. Oxford University Press Oxford UK 149--269.","key":"e_1_2_2_7_1"},{"unstructured":"Baeten J. and Weijland W. 1990. Process Algebra. Number 18 in Cambridge Tracts in Theoretical Computer Science. Cambridge University Press Cambridge MA.   Baeten J. and Weijland W. 1990. Process Algebra. Number 18 in Cambridge Tracts in Theoretical Computer Science. Cambridge University Press Cambridge MA.","key":"e_1_2_2_8_1"},{"doi-asserted-by":"publisher","key":"e_1_2_2_9_1","DOI":"10.1093\/comjnl\/37.4.243"},{"doi-asserted-by":"crossref","unstructured":"Bergstra J. Fokkink W. and Ponse A. 2001. Process algebra with recursive operations. In Handbook of Process Algebra J. Bergstra A. Ponse and S. Smolka Eds. Elsevier Science Amsterdam The Netherlands 333--390.  Bergstra J. Fokkink W. and Ponse A. 2001. Process algebra with recursive operations. In Handbook of Process Algebra J. Bergstra A. Ponse and S. Smolka Eds. Elsevier Science Amsterdam The Netherlands 333--390.","key":"e_1_2_2_10_1","DOI":"10.1016\/B978-044482830-9\/50023-0"},{"key":"e_1_2_2_11_1","volume-title":"Proceedings 11th ICALP, J. Paredaens, Ed. Lecture Notes in Computer Science","volume":"172","author":"Bergstra J.","unstructured":"Bergstra , J. , and Klop , J . 1984. The algebra of recursively defined processes and the algebra of regular processes . In Proceedings 11th ICALP, J. Paredaens, Ed. Lecture Notes in Computer Science , vol. 172 . Springer-Verlag, New York, 82--95. Bergstra, J., and Klop, J. 1984. The algebra of recursively defined processes and the algebra of regular processes. In Proceedings 11th ICALP, J. Paredaens, Ed. Lecture Notes in Computer Science, vol. 172. Springer-Verlag, New York, 82--95."},{"volume-title":"Grammars modulo bisimulation. Ph","author":"Bosscher D.","unstructured":"Bosscher , D. 1997. Grammars modulo bisimulation. Ph . D. University of Amsterdam , Amsterdam, The Netherlands. Bosscher, D. 1997. Grammars modulo bisimulation. Ph.D. University of Amsterdam, Amsterdam, The Netherlands.","key":"e_1_2_2_12_1"},{"key":"e_1_2_2_13_1","volume-title":"Proceedings FICS","author":"Corradini F.","year":"2000","unstructured":"Corradini , F. 2000 . A step forward towards equational axiomatizations of Milner bisimulation in Kleene star . In Proceedings FICS 2000. Corradini, F. 2000. A step forward towards equational axiomatizations of Milner bisimulation in Kleene star. In Proceedings FICS 2000."},{"doi-asserted-by":"publisher","key":"e_1_2_2_14_1","DOI":"10.1093\/logcom\/12.2.301"},{"doi-asserted-by":"publisher","key":"e_1_2_2_15_1","DOI":"10.1016\/S0304-3975(02)00774-0"},{"doi-asserted-by":"publisher","key":"e_1_2_2_16_1","DOI":"10.1307\/mmj\/1028998975"},{"doi-asserted-by":"publisher","key":"e_1_2_2_17_1","DOI":"10.1016\/0022-0000(83)90031-4"},{"key":"e_1_2_2_18_1","volume-title":"Proceedings of Logics for Concurrency: Automata versus Structure. The VIII Banff Higher Order Workshop, G. Birtwistle and F. Moller, Eds. Lecture Notes in Computer Science","volume":"1043","author":"Hirshfeld Y.","unstructured":"Hirshfeld , Y. , and Moller , F . 1996. Decidability results in automata and process theory . In Proceedings of Logics for Concurrency: Automata versus Structure. The VIII Banff Higher Order Workshop, G. Birtwistle and F. Moller, Eds. Lecture Notes in Computer Science , vol. 1043 . Springer-Verlag, New York, 102--148. Hirshfeld, Y., and Moller, F. 1996. Decidability results in automata and process theory. In Proceedings of Logics for Concurrency: Automata versus Structure. The VIII Banff Higher Order Workshop, G. Birtwistle and F. Moller, Eds. Lecture Notes in Computer Science, vol. 1043. Springer-Verlag, New York, 102--148."},{"key":"e_1_2_2_19_1","first-page":"497","article-title":"On the star height of unary regular behaviours. In Proof, Language, and Interaction (Essays in Honour of Robin Milner), G. Plotkin, C. Stirling, and M. Tofte, Eds. Foundations of Computing. MIT Press, Cambridge, MA","volume":"16","author":"Hirshfeld Y.","year":"2000","unstructured":"Hirshfeld , Y. , and Moller , F. 2000 . On the star height of unary regular behaviours. In Proof, Language, and Interaction (Essays in Honour of Robin Milner), G. Plotkin, C. Stirling, and M. Tofte, Eds. Foundations of Computing. MIT Press, Cambridge, MA , Chapter 16 , 497 -- 509 . Hirshfeld, Y., and Moller, F. 2000. On the star height of unary regular behaviours. In Proof, Language, and Interaction (Essays in Honour of Robin Milner), G. Plotkin, C. Stirling, and M. Tofte, Eds. Foundations of Computing. MIT Press, Cambridge, MA, Chapter 16, 497--509.","journal-title":"Chapter"},{"volume-title":"Communicating Sequential Processes","author":"Hoare C.","unstructured":"Hoare , C. 1985. Communicating Sequential Processes . Prentice-Hall , Englewood Cliffs, NJ . Hoare, C. 1985. Communicating Sequential Processes. Prentice-Hall, Englewood Cliffs, NJ.","key":"e_1_2_2_20_1"},{"doi-asserted-by":"publisher","key":"e_1_2_2_22_1","DOI":"10.1016\/0022-0000(84)90023-0"},{"volume-title":"Communication and Concurrency","author":"Milner R.","unstructured":"Milner , R. 1989. Communication and Concurrency . Prentice Hall , Englewood Cliffs, NJ . Milner, R. 1989. Communication and Concurrency. Prentice Hall, Englewood Cliffs, NJ.","key":"e_1_2_2_23_1"},{"doi-asserted-by":"publisher","key":"e_1_2_2_24_1","DOI":"10.1016\/0890-5401(92)90063-L"},{"key":"e_1_2_2_25_1","first-page":"17","article-title":"A structural approach to operational semantics","volume":"60","author":"Plotkin G.","year":"2004","unstructured":"Plotkin , G. 2004 . A structural approach to operational semantics . J. Logic Algeb. Prog. 60 , 17 -- 139 . (Reprint from 1981 in Special Issue on Structural Operational Semantics.) Plotkin, G. 2004. A structural approach to operational semantics. J. Logic Algeb. Prog. 60, 17--139. (Reprint from 1981 in Special Issue on Structural Operational Semantics.)","journal-title":"J. Logic Algeb. Prog."},{"doi-asserted-by":"publisher","key":"e_1_2_2_26_1","DOI":"10.1016\/S0304-3975(00)00285-1"},{"doi-asserted-by":"publisher","key":"e_1_2_2_27_1","DOI":"10.1016\/S0168-0072(97)00036-5"},{"doi-asserted-by":"publisher","key":"e_1_2_2_28_1","DOI":"10.1016\/S0304-3975(00)00389-3"},{"volume-title":"Term Rewriting Systems. Number 55 in Cambridge Tracts in Theoretical Computer Science","author":"TeReSe","unstructured":"TeReSe . 2003. Term Rewriting Systems. Number 55 in Cambridge Tracts in Theoretical Computer Science . Cambridge University Press . TeReSe. 2003. Term Rewriting Systems. Number 55 in Cambridge Tracts in Theoretical Computer Science. Cambridge University Press.","key":"e_1_2_2_29_1"},{"doi-asserted-by":"publisher","key":"e_1_2_2_30_1","DOI":"10.1017\/S0960129500000116"},{"key":"e_1_2_2_31_1","article-title":"Syntax and consistent equation semantics of hybrid chi","volume":"68","author":"van Beek D.","year":"2006","unstructured":"van Beek , D. , Man , K. , Reniers , M. , Rooda , J. , and Schiffelers , R. 2006 . Syntax and consistent equation semantics of hybrid chi . J. Logic Algeb. Prog. 68 , 1\/2, 129--210. van Beek, D., Man, K., Reniers, M., Rooda, J., and Schiffelers, R. 2006. Syntax and consistent equation semantics of hybrid chi. J. Logic Algeb. Prog. 68, 1\/2, 129--210.","journal-title":"J. Logic Algeb. Prog."},{"volume-title":"Handbook of Process Algebra","author":"van Glabbeek R.","unstructured":"van Glabbeek , R. 2001. The linear time---Branching time spectrum I. The semantics of concrete, sequential processes . In Handbook of Process Algebra , J. Bergstra, A. Ponse, and S. Smolka, Eds. Elsevier Science , Amsterdam, The Netherlands, 3--100. van Glabbeek, R. 2001. The linear time---Branching time spectrum I. The semantics of concrete, sequential processes. In Handbook of Process Algebra, J. Bergstra, A. Ponse, and S. Smolka, Eds. Elsevier Science, Amsterdam, The Netherlands, 3--100.","key":"e_1_2_2_32_1"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1219092.1219094","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1219092.1219094","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:42Z","timestamp":1750278162000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1219092.1219094"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,4]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2007,4]]}},"alternative-id":["10.1145\/1219092.1219094"],"URL":"https:\/\/doi.org\/10.1145\/1219092.1219094","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2007,4]]},"assertion":[{"value":"2007-04-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}