# On Varieties of Literally Idempotent Languages

RAIRO - Theoretical Informatics and Applications (2008)

- Volume: 42, Issue: 3, page 583-598
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topKlíma, Ondřej, and Polák, Libor. "On Varieties of Literally Idempotent Languages." RAIRO - Theoretical Informatics and Applications 42.3 (2008): 583-598. <http://eudml.org/doc/250328>.

@article{Klíma2008,

abstract = {
A language L ⊆A* is literally idempotent in case that
ua2v ∈ 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\dots B^*_k$ where B1,...,Bk are
subsets of a given alphabet A.
},

author = {Klíma, Ondřej, Polák, Libor},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Literally idempotent languages; varieties of languages.; varieties of languages},

language = {eng},

month = {6},

number = {3},

pages = {583-598},

publisher = {EDP Sciences},

title = {On Varieties of Literally Idempotent Languages},

url = {http://eudml.org/doc/250328},

volume = {42},

year = {2008},

}

TY - JOUR

AU - Klíma, Ondřej

AU - Polák, Libor

TI - On Varieties of Literally Idempotent Languages

JO - RAIRO - Theoretical Informatics and Applications

DA - 2008/6//

PB - EDP Sciences

VL - 42

IS - 3

SP - 583

EP - 598

AB -
A language L ⊆A* is literally idempotent in case that
ua2v ∈ 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\dots B^*_k$ where B1,...,Bk are
subsets of a given alphabet A.

LA - eng

KW - Literally idempotent languages; varieties of languages.; varieties of languages

UR - http://eudml.org/doc/250328

ER -

## References

top- J. Almeida, Finite Semigroups and Universal Algebra. World Scientific (1994). Zbl0844.20039
- J. Cohen, J.-E. Pin and D. Perrin, On the expressive power of temporal logic. J. Comput. System Sci.46 (1993) 271–294. Zbl0784.03014
- 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. Zbl1015.03025
- Z. Ésik and M. Ito, Temporal logic with cyclic counting and the degree of aperiodicity of finite automata. Acta Cybernetica16 (2003) 1–28. Zbl1027.68074
- Z. Ésik and K.G. Larsen, Regular languages defined by Lindström quantifiers. RAIRO-Theor. Inf. Appl.37 (2003) 197–242.
- A. Kučera and J. Strejček, The stuttering principle revisited. Acta Informatica41 (2005) 415–434. Zbl1079.03008
- M. Kunc, Equationaltion of pseudovarieties of homomorphisms. RAIRO-Theor. Inf. Appl.37 (2003) 243–254. Zbl1045.20049
- D. Peled and T. Wilke, Stutter-invariant temporal properties are expressible without the next-time operator. Inform. Process. Lett.63 (1997) 243–246. Zbl06588308
- J.-E. Pin, Varieties of Formal Languages. Plenum (1986).
- J.-E. Pin, Syntactic semigroups, Chapter 10 in Handbook of Formal Languages, edited by G. Rozenberg and A. Salomaa, Springer (1997).
- H. Straubing, On logical descriptions of recognizable languages, Proc. Latin 2002. Lecture Notes Comput. Sci. 2286 (2002) 528–538. Zbl1059.03034
- D. Thérien and T. Wilke, Nesting until and since in linear temporal logic. Theor. Comput. Syst.37 (2003) 111–131. Zbl1130.03014
- S. Yu, Regular languages, Chapter 2 in Handbook of Formal Languages, edited by G. Rozenberg and A. Salomaa, Springer (1997).

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.