Polynomial closure and unambiguous product |
| |
Authors: | J -E Pin P Weil |
| |
Affiliation: | (1) LITP/IBP, Université Paris VI et CNRS, Tour 55-65, 4 Place Jussieu, 75252 Paris Cedex 05, France |
| |
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 languagesC is the set of languages that are finite unions of languages of the formL
0
a
1
L
1 ···a
nLn, where thea
i’s are letters and theL
i’s are elements ofC. 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 Mal’cev 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 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 us to extend the results of Thomas on quantifier hierarchies of first-order logic. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|