Polynomial closure and unambiguous product

Jean-Éric Pin et Pascal Weil


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. Systems 30, (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.




Valid HTML 4.01!