This paper was published in the proceedings of the
22th ICALP, Berlin, 1995, pp. 348-359, Lecture Notes in Computer
Science 944, Springer Verlag. PostScript gzipped
file, PDF
file
The full version of this paper appeared in Theory Comput. Systems30, (1997), 1-39. Abstract,
PostScript gzipped file, PDF file
Résumé : Cet article est une contribution à la
théorie algébrique des automates, mais contient aussi des
applications au "calcul séquentiel" de Büchi. La fermeture
polynomiale d'une classe de languages C est l'ensemble des
langages qui peuvent s'écrire comme union finie de langages de la
forme L0a1L1...
anLn, où les ai sont des
lettres et les Li sont des éléments de
C. Notre résultat principal est une
caractérisation algébrique, via le monoïde syntactique
ordonné, de la fermeture polynomiale d'une variété de
langages. Nous montrons que l'opération algébrique
correspondant à la fermeture polynomiale est un produit de Malcev
bien particulier. Ce résultat a plusieurs conséquences. Nous
commençons par étudier les hiérarchies de
concaténation similiares à la "dot-depth", obtenues en
comptant le nombre d'alternances entre les opérations
booléennes et le produit de concaténation. Par exemple, nous
montrons que le niveau 3/2 de la hiérarchie de Straubing est
décidable et nous donnons une preuve simplifiée d'un
résultat partiel de Cowan sur le niveau 2. Nous proposons une
conjecture générale pour ces hiérarchies. Nous
montrons également que si un langage et son complément sont
dans la fermeture polynomiale d'une variété de langages,
alors ce langage peut s'écrire comme union disjointe de produits non
ambigus de langages de cette variété. Ceci permet
d'étendre les résultats de Thomas sur les hiérarchies
de quantification de la logique du premier ordre.
Abstract : This article is a contribution to the algebraic theory of
automata, but it also contains an application to Büchi's sequential
calculus. The polynomial closure of a class of languages C is
the set of languages that are finite unions of languages of the form
L0a1L1...
anLn, where the ai's are
letters and the Li's are elements of C. Our
main result is an algebraic characterization, via the ordered syntactic
monoid, of the polynomial closure of a variety of languages. We show that
the algebraic operation corresponding to the polynomial closure is a
certain Malcev product of varieties. This result has several consequences.
We first study the concatenation hierarchies similar to the dot-depth
hierarchy, obtained by counting the number of alternations between boolean
operations and concatenation. For instance, we show that the level 3/2 of
the Straubing hierarchy is decidable and we give a simplified proof of the
partial result of Cowan on level 2. We propose a general conjecture for
these hierarchies. We also show that if a language and its complement are
in the polynomial closure of a variety of languages, then this language can
be written as a disjoint union of marked unambiguous products of languages
of the variety. This allows to extend the results of Thomas on quantifier
hierarchies of first order logic.