Polynomial closure of group languages

Jean-Éric Pin



Résumé : Le résultat principal de cet article affirme qu'un langage reconnaissable est ouvert dans la topologie de Hall si et seulement si il appartient à la fermeture polynomiale C des langages à groupe. Un langage à groupe est un langage reconnaissable reconnu par un automate de permutations. La fermeture polynomiale d'une classe de langages L est l'ensemble des langages qui sont unions finies de langages de la forme L0a1L1 ... anLn, où les ai sont des lettres et les Li sont des éléments de L . La topologie de Hall est la topologie dans laquelle les ouverts sont union (finie ou infinie) de langages à groupe. On donne aussi une description combinatoire de ces langages ainsi qu'une caractérisation syntactique. Soit L un langage reconnaissable de A*, soit M son monoïde syntactique et soit P son image syntactique. Alors L appartient à C si et seulement si, pour tout s, t dans M et pour tout idempotent e de M, st dans P entraine set dans P. Finalement, on donne une caractérisation sur l'automate minimal de L qui conduit à un algorithme en temps polynomial pour tester, étant donné un automate fini deterministe, s'il reconnaît un langage de C.

Abstract : This main result of this paper states that a recognizable language is open in the Hall topology if and only if it belongs to the polynomial closure C of the group languages. A group language is a recognizable language accepted by a permutation automaton. The polynomial closure of a class of languages L 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 L. The Hall topology is the topology in which the open sets are finite or infinite unions of group languages. We also give a combinatorial description of these languages and a syntactic characterization. Let L be a recognizable set of A*, let M be its syntactic monoid and let P be its syntactic image. Then L belongs to C if and only if, for every s, t in M and for every idempotent e of M, st in P implies set in P. Finally, we give a characterization on the minimal automaton of L that leads to a polynomial time algorithm to check, given a finite deterministic automaton, whether it recognizes of C.



Valid HTML 4.01!