On varieties of literally idempotent languages
Klíma, Ondřej ; Polák, Libor
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008), p. 583-598 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

A language L⊆A * is literally idempotent in case that ua 2 v∈L if and only if uav∈L, for each u,v∈A * , a∈A. Varieties of literally idempotent languages result naturally by taking all literally idempotent languages in a classical (positive) variety or by considering a certain closure operator on classes of languages. We initiate the systematic study of such varieties. Various classes of literally idempotent languages can be characterized using syntactic methods. A starting example is the class of all finite unions of B 1 * B 2 * ⋯B k * where B 1 ,⋯,B k are subsets of a given alphabet A.

Publié le : 2008-01-01
DOI : https://doi.org/10.1051/ita:2008020
Classification:  68Q45 
@article{ITA_2008__42_3_583_0,
     author = {Kl\'\i ma, Ond\v rej and Pol\'ak, Libor},
     title = {On varieties of literally idempotent languages},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {42},
     year = {2008},
     pages = {583-598},
     doi = {10.1051/ita:2008020},
     mrnumber = {2434036},
     zbl = {1151.68032},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2008__42_3_583_0}
}

Klíma, Ondřej; Polák, Libor. On varieties of literally idempotent languages. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) pp. 583-598. doi : 10.1051/ita:2008020. http://gdmltest.u-ga.fr/item/ITA_2008__42_3_583_0/

[1] J. Almeida, Finite Semigroups and Universal Algebra. World Scientific (1994). | MR 1331143 | Zbl 0844.20039

[2] J. Cohen, J.-E. Pin and D. Perrin, On the expressive power of temporal logic. J. Comput. System Sci. 46 (1993) 271-294. | MR 1228808 | Zbl 0784.03014

[3] Z. Ésik, Extended temporal logic on finite words and wreath product of monoids with distinguished generators, Proc. DLT 02. Lect. Notes Comput. Sci. 2450 (2003) 43-58. | MR 2177331 | Zbl 1015.03025

[4] Z. Ésik and M. Ito, Temporal logic with cyclic counting and the degree of aperiodicity of finite automata. Acta Cybernetica 16 (2003) 1-28. | MR 1990143 | Zbl 1027.68074

[5] Z. Ésik and K.G. Larsen, Regular languages defined by Lindström quantifiers. RAIRO-Theor. Inf. Appl. 37 (2003) 197-242. | Numdam | Zbl 1046.20042

[6] A. Kučera and J. Strejček, The stuttering principle revisited. Acta Informatica 41 (2005) 415-434. | MR 2150128 | Zbl 1079.03008

[7] M. Kunc, Equationaltion of pseudovarieties of homomorphisms. RAIRO-Theor. Inf. Appl. 37 (2003) 243-254. | Numdam | MR 2021316 | Zbl 1045.20049

[8] D. Peled and T. Wilke, Stutter-invariant temporal properties are expressible without the next-time operator. Inform. Process. Lett. 63 (1997) 243-246. | MR 1475336

[9] J.-E. Pin, Varieties of Formal Languages. Plenum (1986). | MR 912694 | Zbl 0632.68069

[10] J.-E. Pin, Syntactic semigroups, Chapter 10 in Handbook of Formal Languages, edited by G. Rozenberg and A. Salomaa, Springer (1997). | MR 1470002

[11] H. Straubing, On logical descriptions of recognizable languages, Proc. Latin 2002. Lecture Notes Comput. Sci. 2286 (2002) 528-538. | MR 1966148 | Zbl 1059.03034

[12] D. Thérien and T. Wilke, Nesting until and since in linear temporal logic. Theor. Comput. Syst. 37 (2003) 111-131. | MR 2038405 | Zbl 1130.03014

[13] S. Yu, Regular languages, Chapter 2 in Handbook of Formal Languages, edited by G. Rozenberg and A. Salomaa, Springer (1997). | MR 1470017