An algebraic representation of the fixed-point closure of *-continuous Kleene algebras – A categorical Chomsky–Schützenberger theorem

Leiß, Hans (2022): An algebraic representation of the fixed-point closure of *-continuous Kleene algebras – A categorical Chomsky–Schützenberger theorem. In: Mathematical Structures in Computer Science, Bd. 32, Nr. Special issue 6: S. 685-728

Abstract

The family RX∗ of regular subsets of the free monoid X∗ generated by a finite set X is the standard example of a ∗ -continuous Kleene algebra. Likewise, the family CX∗ of context-free subsets of X∗ is the standard example of a μ -continuous Chomsky algebra, i.e. an idempotent semiring that is closed under a well-behaved least fixed-point operator μ . For arbitrary monoids M, CM is the closure of RM as a μ -continuous Chomsky algebra, more briefly, the fixed-point closure of RM . We provide an algebraic representation of CM in a suitable product of RM with C′2 , a quotient of the regular sets over an alphabet Δ2 of two pairs of bracket symbols. Namely, CM is isomorphic to the centralizer of C′2 in the product of RM with C′2 , i.e. the set of those elements that commute with all elements of C′2 . This generalizes a well-known result of Chomsky and Schützenberger (1963, Computer Programming and Formal Systems, 118–161) and admits us to denote all context-free languages over finite sets X⊆M by regular expressions over X∪Δ2 interpreted in the product of RM and C′2 . More generally, for any ∗ -continuous Kleene algebra K the fixed-point closure of K can be represented algebraically as the centralizer of C′2 in the product of K with C′2 .

• Dokumententyp: Zeitschriftenartikel
• Fakultätsübergreifende Einrichtungen: Centrum für Informations- und Sprachverarbeitung (CIS)
• Themengebiete: 400 Sprache > 400 Sprache
• ISSN: 0960-1295
• Sprache: Englisch