An Algebraic Representation of the Fixed-Point Closure of *-continuous Kleene Algebras

Speaker:  Dr. Hans LeiƟ - (LMU Munich, retired)
  Tuesday, May 9, 2023 at 4:30 PM Aula Gino Tessari (solo presenza)

Abstract: The theorem of Chomsky and Schützenberger says that each context-free language L over a finite alphabet X is the image of the intersection of a regular language R over X+Y and the context-free Dyck-language D over X+Y of strings with balanced brackets from Y under the bracket-erasing homomorphism from the monoid of strings over X+Y to that of strings over X. Within Hopkins' algebraization of formal language theory we show that the algebra C(X) of context-free languages over X has an isomorphic copy in a suitable tensor product of the algebra R(X) of regular languages over X with a quotient of R(Y) by a congruence describing bracket matches and mismatches. It follows that all context-free languages over X can be defined by regular(!) expressions over X+Y where the letters of X commute with the brackets of Y, thereby providing a substitute for a fixed-point-operator. This generalizes the theorem of Chomsky and Schützenberger and leads to an algebraic representation of the fixed-point closure of *-continuous Kleene algebras.

 

 


Programme Director
Peter Michael Schuster

Publication date
April 28, 2023

Studying

Share