Previous |  Up |  Next


Title: A classification of rational languages by semilattice-ordered monoids (English)
Author: Polák, Libor
Language: English
Journal: Archivum Mathematicum
ISSN: 0044-8753 (print)
ISSN: 1212-5059 (online)
Volume: 40
Issue: 4
Year: 2004
Pages: 395-406
Summary lang: English
Category: math
Summary: 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. (English)
Keyword: syntactic semilattice-ordered monoid
Keyword: conjunctive varieties of rational languages
MSC: 06F05
MSC: 08A70
MSC: 16Y60
MSC: 20M07
MSC: 68Q70
idZBL: Zbl 1112.68098
idMR: MR2129961
Date available: 2008-06-06T22:44:38Z
Last updated: 2012-05-10
Stable URL:
Reference: [1] Almeida J.: Finite Semigroups and Universal Algebra.World Scientific, 1994. Zbl 0844.20039, MR 1331143
Reference: [2] Eilenberg S.: Automata, Languages and Machines.Vol. B, Academic Press, 1976. Zbl 0359.94067, MR 0530383
Reference: [3] Myhill J.: Finite automata and the representation of events.WADD Techn. Report 57–624, Wright Patterson Air Force Base, 1957.
Reference: [4] Pin J.-E.: Varieties of Formal Languages.Plenum, 1986. Zbl 0632.68069, MR 0912694
Reference: [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 1391325
Reference: [6] Polák L.: Syntactic semiring of a Proc. Mathematical Foundation of Computer Science 2001, Lecture Notes in Comput. Sci., Vol. 2136 (2001), 611–620. Zbl 1005.68526
Reference: [7] Polák L.: Operators on Classes of Regular Algorithms, Automata and Languages, J.P.G. Gomes and P. Silva (ed.), World Scientific (2002), 407–422. MR 2023799
Reference: [8] Polák L.: Syntactic Semiring and Language 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 2047726
Reference: [9] Straubing H.: On logical descriptions of regular Proc. LATIN 2002, Lecture Notes in Comput. Sci., Vol. 2286 (2002), 528–538. Zbl 1059.03034, MR 1966148


Files Size Format View
ArchMathRetro_040-2004-4_8.pdf 246.0Kb application/pdf View/Open
Back to standard record
Partner of
EuDML logo