Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
Equations Defining the Polynomial Closure of a Lattice of Regular Languages
verfasst von : Mário J. J. Branco, Jean-Éric Pin
Erschienen in: Automata, Languages and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The
polynomial closure
Pol
$(\mathcal{L})$
of a class of languages
$\mathcal{L}$
of
A
*
is the set of languages that are finite unions of marked products of the form
L
0
a
1
L
1
...
a
n
L
n
, where the
a
i
are letters and the
L
i
are elements of
$\mathcal{L}$
.
The main result of this paper gives an equational description of Pol
$(\mathcal{L})$
, given an equational description of
$\mathcal{L}$
, when
$\mathcal{L}$
is a lattice of regular languages closed under quotients, or a
quotienting algebra of languages
, as we call it in the sequel. The term “equational description” refers to a recent paper [5], where it was shown that any lattice of regular languages can be defined by a set of profinite equations. More formally, our main result can be stated as follows: