| 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:
|
http://hdl.handle.net/10338.dmlcz/107923 |
| . |
| 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 language.in 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 Languages.in 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 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 |
| Reference:
|
[9] Straubing H.: On logical descriptions of regular languages.in Proc. LATIN 2002, Lecture Notes in Comput. Sci., Vol. 2286 (2002), 528–538. Zbl 1059.03034, MR 1966148 |
| . |
