On Varieties of Literally Idempotent Languages

Ondřej Klíma; Libor Polák

RAIRO - Theoretical Informatics and Applications (2008)

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

Abstract

top
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 * ⋯ B k * where B1,...,Bk are subsets of a given alphabet A.

How to cite

top

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

NotesEmbed ?

top

You must be logged in to post comments.