- Seminars
- An Algebraic Representation of the Fixed-Point Closure of *-continuous Kleene Algebras
An Algebraic Representation of the Fixed-Point Closure of *-continuous Kleene Algebras
Speaker
Dr. Hans Leiß - (LMU Munich, retired)
Date
May 9, 2023 - Time:
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
- Apr 28, 2023
- Contact person
- Peter Michael Schuster
- Department
- Computer Science