{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T21:57:28Z","timestamp":1747173448261,"version":"3.40.5"},"reference-count":21,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2022,10,14]],"date-time":"2022-10-14T00:00:00Z","timestamp":1665705600000},"content-version":"unspecified","delay-in-days":135,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[2022,6]]},"abstract":"Abstract<\/jats:title>The family \n${\\mathcal{R}} X^*$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> of regular subsets of the free monoid \n$X^*$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> generated by a finite set X<\/jats:italic> is the standard example of a \n${}^*$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-continuous Kleene algebra. Likewise, the family \n${\\mathcal{C}} X^*$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> of context-free subsets of \n$X^*$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is the standard example of a \n$\\mu$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-continuous Chomsky algebra, i.e. an idempotent semiring that is closed under a well-behaved least fixed-point operator \n$\\mu$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. For arbitrary monoids M<\/jats:italic>, \n${\\mathcal{C}} M$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is the closure of \n${\\mathcal{R}}M$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> as a \n$\\mu$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-continuous Chomsky algebra, more briefly, the fixed-point closure of \n${\\mathcal{R}} M$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. We provide an algebraic representation of \n${\\mathcal{C}} M$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> in a suitable product of \n${\\mathcal{R}} M$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> with \n$C_2'$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, a quotient of the regular sets over an alphabet \n$\\Delta_2$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> of two pairs of bracket symbols. Namely, \n${\\mathcal{C}}M$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is isomorphic to the centralizer of \n$C_2'$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> in the product of \n${\\mathcal{R}} M$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> with \n$C_2'$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, i.e. the set of those elements that commute with all elements of \n$C_2'$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. This generalizes a well-known result of Chomsky and Sch\u00fctzenberger (1963, Computer Programming and Formal Systems<\/jats:italic>, 118\u2013161) and admits us to denote all context-free languages over finite sets \n$X\\subseteq M$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> by regular expressions over \n$X\\cup\\Delta_2$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> interpreted in the product of \n${\\mathcal{R}} M$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and \n$C_2'$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. More generally, for any \n${}^*$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-continuous Kleene algebra K<\/jats:italic> the fixed-point closure of K<\/jats:italic> can be represented algebraically as the centralizer of \n$C_2'$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> in the product of K<\/jats:italic> with \n$C_2'$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1017\/s0960129522000329","type":"journal-article","created":{"date-parts":[[2022,10,14]],"date-time":"2022-10-14T08:57:04Z","timestamp":1665737824000},"page":"685-728","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":1,"title":["An algebraic representation of the fixed-point closure of *-continuous Kleene algebras \u2013 A categorical Chomsky\u2013Sch\u00fctzenberger theorem"],"prefix":"10.1017","volume":"32","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4162-2258","authenticated-orcid":false,"given":"Hans","family":"Lei\u00df","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2022,10,14]]},"reference":[{"key":"S0960129522000329_ref17","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-9839-7","volume-title":"Categories for the Working Mathematician","author":"Mac Lane","year":"1971"},{"key":"S0960129522000329_ref8","doi-asserted-by":"crossref","unstructured":"Hopkins, M. (2008b). The algebraic approach II: Dioids, quantales and monads. In: Berghammer, R., M\u00f6ller, B. and Struth, G. (eds.) Relational Methods in Computer Science\/Applications of Kleene Algebra, LNCS, vol. 4988, Berlin Heidelberg, Springer Verlag, 173\u2013190.","DOI":"10.1007\/978-3-540-78913-0_14"},{"key":"S0960129522000329_ref4","unstructured":"Hopkins, M. (1993). The Untold Story of Formal Languages. Submissions to USENET forum comp.theory (1993\/95) and sci.math.research Jan.\/Feb. 1996."},{"key":"S0960129522000329_ref12","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0029594"},{"key":"S0960129522000329_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-02149-8_3"},{"key":"S0960129522000329_ref14","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1037"},{"key":"S0960129522000329_ref5","unstructured":"Hopkins, M. (2006). The Theory of Context-Free Expressions. Unpublished Typoscript. Partly based on submissions to USENET forum comp.theory, May 2004."},{"key":"S0960129522000329_ref7","doi-asserted-by":"crossref","unstructured":"Hopkins, M. (2008a). The algebraic approach I: The algebraization of the Chomsky hierarchy. In: Berghammer, R., M\u00f6ller, B. and Struth, G. (eds.) Relational Methods in Computer Science\/Applications of Kleene Algebra, LNCS, vol. 4988, Berlin Heidelberg, Springer Verlag, 155\u2013172.","DOI":"10.1007\/978-3-540-78913-0_13"},{"key":"S0960129522000329_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-02149-8_2"},{"key":"S0960129522000329_ref18","unstructured":"Nivat, M. and Perrot, J.-F. (1970). Une g\u00e9neralisation du monoide bicyclique. C.R.Acad.Sci. Paris, S\u00e9r A 271."},{"key":"S0960129522000329_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)72023-8"},{"key":"S0960129522000329_ref6","doi-asserted-by":"crossref","unstructured":"Hopkins, M. (2007). CEX - A Context-Free Expression Filter. https:\/\/compilers.iecc.com\/comparch\/article\/07-02-067.","DOI":"10.1088\/1126-6708\/2007\/02\/067"},{"volume-title":"The Design and Analysis of Algorithms","year":"1991","author":"Kozen","key":"S0960129522000329_ref13"},{"key":"S0960129522000329_ref11","doi-asserted-by":"crossref","unstructured":"Kozen, D. (1981). On induction vs. $^*$ -continuity. In: Kozen, D. (ed.) Proceedings of the Workshop on Logics of Programs 1981, Lecture Notes in Computer Science, vol. 131, Springer Verlag, 167\u2013176.","DOI":"10.1007\/BFb0025782"},{"key":"S0960129522000329_ref15","unstructured":"Lei\u00df, H. (2016). The matrix ring of a $\\mu$ -continuous Chomsky algebra is $\\mu$ -continuous. In: Regnier, L. and Talbot, J.-M. (eds.) 25th EACSL Annual Conference on Computer Science Logic (CSL 2016), Leibniz International Proceedings in Informatics, Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl Publishing, 1\u201316."},{"volume-title":"Quantales and Their Applications","year":"1990","author":"Rosenthal","key":"S0960129522000329_ref20"},{"volume-title":"EATCS Monographs","year":"1998","author":"Sikkel","key":"S0960129522000329_ref21"},{"key":"S0960129522000329_ref19","doi-asserted-by":"crossref","first-page":"1329","DOI":"10.1016\/j.ic.2009.02.012","article-title":"Rational subsets of polycyclic monoids and valence automata","volume":"207","author":"Render","year":"2009","journal-title":"Information and Computation"},{"volume-title":"Regular Algebra and Finite Machines","year":"1971","author":"Conway","key":"S0960129522000329_ref2"},{"key":"S0960129522000329_ref3","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.126.4"},{"key":"S0960129522000329_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-20095-3_14"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129522000329","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,8]],"date-time":"2023-03-08T09:49:28Z","timestamp":1678268968000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129522000329\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6]]},"references-count":21,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["S0960129522000329"],"URL":"https:\/\/doi.org\/10.1017\/s0960129522000329","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"type":"print","value":"0960-1295"},{"type":"electronic","value":"1469-8072"}],"subject":[],"published":{"date-parts":[[2022,6]]},"assertion":[{"value":"\u00a9 The Author(s), 2022. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http:\/\/creativecommons.org\/licenses\/by\/4.0\/), which permits unrestricted re-use, distribution and reproduction, provided the original article is properly cited.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}