A classification of rational languages by semilattice-ordered monoids
Polák, Libor
Archivum Mathematicum, Tome 040 (2004), p. 395-406 / Harvested from Czech Digital Mathematics Library
Access to full text
Full (PDF)

We prove here an Eilenberg type theorem: the so-called conjunctive varieties of rational languages correspond to the pseudovarieties of finite semilattice-ordered monoids. Taking complements of members of a conjunctive variety of languages we get a so-called disjunctive variety. We present here a non-trivial example of such a variety together with an equational characterization of the corresponding pseudovariety.

Publié le : 2004-01-01
Classification:  06F05,  08A70,  16Y60,  20M07,  68Q70 
@article{107923,
     author = {Libor Pol\'ak},
     title = {A classification of rational languages by semilattice-ordered monoids},
     journal = {Archivum Mathematicum},
     volume = {040},
     year = {2004},
     pages = {395-406},
     zbl = {1112.68098},
     mrnumber = {2129961},
     language = {en},
     url = {http://dml.mathdoc.fr/item/107923}
}

Polák, Libor. A classification of rational languages by semilattice-ordered monoids. Archivum Mathematicum, Tome 040 (2004) pp. 395-406. http://gdmltest.u-ga.fr/item/107923/

Almeida J. Finite Semigroups and Universal Algebra, World Scientific, 1994. (1994) | MR 1331143 | Zbl 0844.20039

Eilenberg S. Automata, Languages and Machines, Vol. B, Academic Press, 1976. (1976) | MR 0530383 | Zbl 0359.94067

Myhill J. Finite automata and the representation of events, WADD Techn. Report 57–624, Wright Patterson Air Force Base, 1957. (1957)

Pin J.-E. Varieties of Formal Languages, Plenum, 1986. (1986) | MR 0912694 | Zbl 0632.68069

Pin J.-E. A variety theorem without complementation, Izvestiya VUZ Matematika 39 (1995), 80–90. English version: Russian Mathem. (Iz. VUZ) 39 (1995), 74–83. (1995) | MR 1391325

Polák L. Syntactic semiring of a language, in Proc. Mathematical Foundation of Computer Science 2001, Lecture Notes in Comput. Sci., Vol. 2136 (2001), 611–620. | Zbl 1005.68526

Polák L. Operators on Classes of Regular Languages, in Algorithms, Automata and Languages, J.P.G. Gomes and P. Silva (ed.), World Scientific (2002), 407–422. | MR 2023799

Polák L. Syntactic Semiring and Language Equations, in Proc. of the Seventh International Conference on Implementation and Application of Automata, Tours 2002, Lecture Notes in Comput. Sci., Vol. 2608 (2003), 182–193. (193.) | MR 2047726

Straubing H. On logical descriptions of regular languages, in Proc. LATIN 2002, Lecture Notes in Comput. Sci., Vol. 2286 (2002), 528–538. | MR 1966148 | Zbl 1059.03034