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

DOI : https://doi.org/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},
zbl = {1151.68032},
mrnumber = {2434036},
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
DA  - 2008///
SP  - 583
EP  - 598
VL  - 42
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2008020/
UR  - https://zbmath.org/?q=an%3A1151.68032
UR  - https://www.ams.org/mathscinet-getitem?mr=2434036
UR  - https://doi.org/10.1051/ita:2008020
DO  - 10.1051/ita:2008020
LA  - en
ID  - ITA_2008__42_3_583_0
ER  - 
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/

[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

Cité par Sources :