On varieties of literally idempotent languages

Klíma, Ondřej; Polák, Libor

doi:10.1051/ita:2008020

Klíma, Ondřej ; Polák, Libor

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) no. 3, pp. 583-598.

Résumé

A language $L \subseteq A^{*}$ is literally idempotent in case that $u a^{2} v \in L$ if and only if $u a v \in L$ , for each $u, v \in A^{*}$ , $a \in 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}^{*} \dots B_{k}^{*}$ where $B_{1}, \dots, B_{k}$ are subsets of a given alphabet $A$ .

MR Zbl

DOI : 10.1051/ita:2008020

Classification : 68Q45
Mots-clés : 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},
     publisher = {EDP-Sciences},
     volume = {42},
     number = {3},
     year = {2008},
     doi = {10.1051/ita:2008020},
     mrnumber = {2434036},
     zbl = {1151.68032},
     language = {en},
     url = {http://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  - http://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 http://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. http://www.numdam.org/articles/10.1051/ita:2008020/

Bibliographie
Cité par

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

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

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

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

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

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

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

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

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

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

[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 :