no. 3
On varieties of literally idempotent languages
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) no. 3, pp. 583-598

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.

DOI : 10.1051/ita:2008020
Classification : 68Q45
Keywords: literally idempotent languages, varieties of languages 
@article{ITA_2008__42_3_583_0,
     author = {Kl{\'\i}ma, Ond\v{r}ej and Pol\'ak, Libor},
     title = {On varieties of literally idempotent languages},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {583--598},
     year = {2008},
     publisher = {EDP Sciences},
     volume = {42},
     number = {3},
     doi = {10.1051/ita:2008020},
     mrnumber = {2434036},
     zbl = {1151.68032},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ita:2008020/}
}
TY  - JOUR
AU  - Klíma, Ondřej
AU  - Polák, Libor
TI  - On varieties of literally idempotent languages
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2008
SP  - 583
EP  - 598
VL  - 42
IS  - 3
PB  - EDP Sciences
UR  - https://www.numdam.org/articles/10.1051/ita:2008020/
DO  - 10.1051/ita:2008020
LA  - en
ID  - ITA_2008__42_3_583_0
ER  - 
%0 Journal Article
%A Klíma, Ondřej
%A Polák, Libor
%T On varieties of literally idempotent languages
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2008
%P 583-598
%V 42
%N 3
%I EDP Sciences
%U https://www.numdam.org/articles/10.1051/ita:2008020/
%R 10.1051/ita:2008020
%G en
%F 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) no. 3, pp. 583-598. doi: 10.1051/ita:2008020

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

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

[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. | Zbl | MR

[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. | Zbl | MR

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

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

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

[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

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

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

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

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

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

Cité par Sources :