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

Relatore
Dr. Hans Leiß - (LMU Munich, retired)

Data
9-mag-2023 - Ora: 16:30 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.

 

 

Data pubblicazione
28-apr-2023

Referente
Peter Michael Schuster
Dipartimento
Informatica