Geodesic
A classification of rational languages by semilattice-ordered monoids
Archivum mathematicum, Tome 40 (2004) no. 4, pp. 395-406 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
Classification : 06F05, 08A70, 16Y60, 20M07, 68Q70
Keywords: syntactic semilattice-ordered monoid; conjunctive varieties of rational languages 
@article{ARM_2004_40_4_a7,
     author = {Pol\'ak, Libor},
     title = {A classification of rational languages by semilattice-ordered monoids},
     journal = {Archivum mathematicum},
     pages = {395--406},
     year = {2004},
     volume = {40},
     number = {4},
     mrnumber = {2129961},
     zbl = {1112.68098},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ARM_2004_40_4_a7/}
}
TY  - JOUR
AU  - Polák, Libor
TI  - A classification of rational languages by semilattice-ordered monoids
JO  - Archivum mathematicum
PY  - 2004
SP  - 395
EP  - 406
VL  - 40
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/ARM_2004_40_4_a7/
LA  - en
ID  - ARM_2004_40_4_a7
ER  - 
%0 Journal Article
%A Polák, Libor
%T A classification of rational languages by semilattice-ordered monoids
%J Archivum mathematicum
%D 2004
%P 395-406
%V 40
%N 4
%U http://geodesic.mathdoc.fr/item/ARM_2004_40_4_a7/
%G en
%F ARM_2004_40_4_a7
Polák, Libor. A classification of rational languages by semilattice-ordered monoids. Archivum mathematicum, Tome 40 (2004) no. 4, pp. 395-406. http://geodesic.mathdoc.fr/item/ARM_2004_40_4_a7/

[1] Almeida J.: Finite Semigroups and Universal Algebra. World Scientific, 1994. | MR | Zbl

[2] Eilenberg S.: Automata, Languages and Machines. Vol. B, Academic Press, 1976. | MR | Zbl

[3] Myhill J.: Finite automata and the representation of events. WADD Techn. Report 57–624, Wright Patterson Air Force Base, 1957.

[4] Pin J.-E.: Varieties of Formal Languages. Plenum, 1986. | MR | Zbl

[5] 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. | MR

[6] 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

[7] 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

[8] 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. | MR

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