Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
syntactic semilattice-ordered monoid; conjunctive varieties of rational languages
syntactic semilattice-ordered monoid; conjunctive varieties of rational languages
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.
References:
[1] Almeida J.: Finite Semigroups and Universal Algebra. World Scientific, 1994. MR 1331143 | Zbl 0844.20039
[2] Eilenberg S.: Automata, Languages and Machines. Vol. B, Academic Press, 1976. MR 0530383 | Zbl 0359.94067
[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 0912694 | Zbl 0632.68069
[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
[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 1005.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. MR 2023799
[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 2047726
[9] Straubing H.: On logical descriptions of regular languages. in Proc. LATIN 2002, Lecture Notes in Comput. Sci., Vol. 2286 (2002), 528–538. MR 1966148 | Zbl 1059.03034
Search
Partner of
