ALGEBRAIC AND TOPOLOGICAL THEORY OF LANGUAGES

Authors
Citation
J. Rhodes et P. Weil, ALGEBRAIC AND TOPOLOGICAL THEORY OF LANGUAGES, Informatique theorique et applications, 29(1), 1995, pp. 1-44
Citations number
23
Categorie Soggetti
Computer Sciences","Computer Science Information Systems
ISSN journal
09883754
Volume
29
Issue
1
Year of publication
1995
Pages
1 - 44
Database
ISI
SICI code
0988-3754(1995)29:1<1:AATTOL>2.0.ZU;2-T
Abstract
A language is torsion (resp. bounded torsion, aperiodic, bounded aperi odic), if its syntactic monoid is torsion (resp. bounded torsion, aper iodic, bounded aperiodic). We generalize the regular language theorems of Klenne, Schutzenberger and Straubing to describe the classes of to rsion, bounded torsion, aperiodic and bounded aperiodic languages. The se descriptions involve taking limits of sequences of languages and au tomata for certain topologies defined by filtrations of the free monoi d. A theorem for arbitrary languages over finite alphabets is also sta ted and proved.