Portal de Periódicos da CAPES

Algebraic and topological theory of languages

1995; EDP Sciences; Volume: 29; Issue: 1 Linguagem: Francês

10.1051/ita/1995290100011

1290-385X

John Rhodes, Pascal Weil,

Computability, Logic, AI Algorithms

A language is torsion (resp.bounded torsion, aperiodic, bounded aperiodic), if ils syntactic monoid is torsion (resp.bounded torsion, aperiodic, bounded aperiodic).We generalize the regular language theorems of Klenne, Schützenberger and Straubing to describe the classes of torsion, bounded torsion, aperiodic and bounded aperiodic languages.These descriptions involve taking limits of séquences of languages and automatafor certain topologies defined by filtrations of thefree monoid.A theoremfor arbitrary languages overfinite alphabets is also stated and proved.Résumé.-On dit qu'un langage est de torsion (resp.de torsion bornée, apériodique, apériodique borné) si son monoïde syntaxique est de torsion (resp.de torsion bornée, apériodique, apériodique borné).Nous généralisons les théorèmes sur les langages rationnels de Kleene, Schützenberger et Straubing pour décrire les classes des langages de torsion, de torsion bornée, apériodiques et apériodiques bornés.Ces descriptions imposent la considération de limites de suites de langages et d'automates pour certaines topologies définies par des filtrations du monoïde libre.Nous donnons également un théorème concernant les langages arbitraires sur des alphabets finis.