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
topHow 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 ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.