A classification of rational languages by semilattice-ordered monoids

Libor Polák

Archivum Mathematicum (2004)

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

Abstract

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

How to cite

top

Polá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
  1. Almeida J., Finite Semigroups and Universal Algebra, World Scientific, 1994. (1994) Zbl0844.20039MR1331143
  2. Eilenberg S., Automata, Languages and Machines, Vol. B, Academic Press, 1976. (1976) Zbl0359.94067MR0530383
  3. Myhill J., Finite automata and the representation of events, WADD Techn. Report 57–624, Wright Patterson Air Force Base, 1957. (1957) 
  4. Pin J.-E., Varieties of Formal Languages, Plenum, 1986. (1986) Zbl0632.68069MR0912694
  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. (1995) MR1391325
  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. Zbl1005.68526
  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. MR2023799
  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. (193.) MR2047726
  9. 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 ?

top

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.