Polynomial closure and unambiguous product

J-E. Pin, P. Weil

IBP-Litp 1994/60: Rapport de Recherche Litp / Litp research reports
40 pages - Octobre/October 1994 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: Polynomial closure and unambiguous product

Résumé : Cet article est une contribution à la théorie algébrique des langages reconnaissables, mais contient également une application aux liens entre la logique et les automates. La fermeture polynomiale d'une classe de langages C est l'ensemble des unions finies de produits marqués de langages de C (i.e. de la forme L0a1L1 ... anLn, où les ai sont des lettres et les Li sont des langages de C ). Le résultat principal de cet article est une caractérisation algébrique, via le monoïde syntactique, de la fermeture polynomiale d'une variété de langages. Nous montrons que l'opération algébrique qui correspond à la fermeture polynomiale est un produit de Malcev de variétés. Ce résultat a de nombreuses conséquences. Nous étudions en particulier les hiérarchies de concaténation, similaires à la "dot-depth" introduite par Brzozowski, obtenues en comptant le nombre d'alternances entre les opérations booléennes et le produit. Nous montrons par exemple que le niveau 3/2 de la hiérarchie de Straubing est décidable et donnons une preuve simplifiée du résultat partiel de Cowan sur le niveau 2. Nous proposons également une nouvelle conjecture générale pour ces hiérarchies. Nous montrons également que si un langage et son complémentaire sont dans la fermeture polynomiale d'une variété de langages, alors ce langage s'exprime comme union disjointe de produits marqués non-ambigus de langages de la variété. Ceci permet d'étendre les résultats de Thomas sur les hiérarchies de quantification de la logique 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 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.

Publications internes Litp 1994 / Litp research reports 1994