Polynomial closure of group languages And Open sets of the Hall topology

J-E. PIN

IBP-Litp 1994/21: Rapport de Recherche Litp / Litp research reports
12 pages - Décembre/December 1994 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: Polynomial closure of group languages And Open sets of the Hall topology

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's sont des lettres et les Li's 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 syntacticque. 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 OE M et pour tout idempotent e de M, st OE P entraine set OE 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 OE M and for every idempotent e of M, st OE P implies set OE 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 .

Publications internes Litp 1994 / Litp research reports 1994