Links und Funktionen
Sprachumschaltung

Navigationspfad
Sie sind hier: Startseite / Lehre / SS 2019 / Oberseminar / Hans Leiß: An Algebraic Generalization of the Chomsky-Schützenberger-Theorem


Inhaltsbereich

Hans Leiß: An Algebraic Generalization of the Chomsky-Schützenberger-Theorem

Oberseminarvortrag von Hans Leiß über An Algebraic Generalization of the Chomsky-Schützenberger-Theorem
Wann 14:15 16:00 10.05.2019
von bis
Wo Raum L109, Oettingenstr. 67
Termin übernehmen vCal
iCal

Es spricht Hans Leiß über:
An Algebraic Generalization of the Chomsky-Schützenberger-Theorem

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 balanced strings 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
image 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 is a
step towards characterizing the algebraic or fixed-point closure of
the algebra R(M) of regular subsets of a monoid M or of a *-continuous
Kleene algebra K by algebraic means.

Artikelaktionen


Funktionsleiste