2009 | OriginalPaper | Chapter
Equations Defining the Polynomial Closure of a Lattice of Regular Languages
Authors : Mário J. J. Branco, Jean-Éric Pin
Published in: Automata, Languages and Programming
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. 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: