Algebraic and topological theory of languages
John Rhodes, Pascal Weil · RAIRO - Theoretical Informatics and Applications · 1995
: A language is torsion (resp. bounded torsion, aperiodic, bounded aperiodic) if its syntactic monoid is torsion (resp. bounded torsion, aperiodic, bounded aperiodic). We generalize the regular language theorems of Kleene, Schutzenberger and Straubing to describe the classes of torsion, bounded torsion, aperiodic and bounded aperiodic languages. These descriptions involve taking limits of sequences of languages and automata for certain topologies defined by filtrations of the free monoid. A theorem for arbitrary languages over finite alphabets is also stated and proved. AMS Mathematics Subject Classification: 68Q45, 68Q70, 20M35. * Both authors gratefully acknowledge support from the first author's National Science Foundation grant DMS88-03362. The second author was also supported in part by the Projet de Recherche Coordonn'ee "Math'ematiques et Informatique". J. Rhodes and P. Weil Introduction The aim of this paper is to generalize the central results of the theory of rational, o...