# A classification of rational languages by semilattice-ordered monoids

Archivum Mathematicum (2004)

- Volume: 040, Issue: 4, page 395-406
- ISSN: 0044-8753

## Access Full Article

top## Abstract

top## How to cite

topPolák, Libor. "A classification of rational languages by semilattice-ordered monoids." Archivum Mathematicum 040.4 (2004): 395-406. <http://eudml.org/doc/249314>.

@article{Polák2004,

abstract = {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.},

author = {Polák, Libor},

journal = {Archivum Mathematicum},

keywords = {syntactic semilattice-ordered monoid; conjunctive varieties of rational languages; syntactic semilattice-ordered monoid; conjunctive varieties of rational languages},

language = {eng},

number = {4},

pages = {395-406},

publisher = {Department of Mathematics, Faculty of Science of Masaryk University, Brno},

title = {A classification of rational languages by semilattice-ordered monoids},

url = {http://eudml.org/doc/249314},

volume = {040},

year = {2004},

}

TY - JOUR

AU - Polák, Libor

TI - A classification of rational languages by semilattice-ordered monoids

JO - Archivum Mathematicum

PY - 2004

PB - Department of Mathematics, Faculty of Science of Masaryk University, Brno

VL - 040

IS - 4

SP - 395

EP - 406

AB - 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.

LA - eng

KW - syntactic semilattice-ordered monoid; conjunctive varieties of rational languages; syntactic semilattice-ordered monoid; conjunctive varieties of rational languages

UR - http://eudml.org/doc/249314

ER -

## References

top- Almeida J., Finite Semigroups and Universal Algebra, World Scientific, 1994. (1994) Zbl0844.20039MR1331143
- Eilenberg S., Automata, Languages and Machines, Vol. B, Academic Press, 1976. (1976) Zbl0359.94067MR0530383
- 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) Zbl0632.68069MR0912694
- 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) MR1391325
- 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. Zbl1005.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. MR2023799
- 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.) MR2047726
- Straubing H., On logical descriptions of regular languages, in Proc. LATIN 2002, Lecture Notes in Comput. Sci., Vol. 2286 (2002), 528–538. Zbl1059.03034MR1966148

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.