RAIRO - Theoretical Informatics and Applications (RAIRO: ITA)

| Abstract | PDF (216.9 KB) | References |

RAIRO-Theor. Inf. Appl. 42, 583-598 (2008)
DOI: 10.1051/ita:2008020

On Varieties of Literally Idempotent Languages

Ondrej Klíma and Libor Polák

Department of Mathematics, Masaryk University, Janáckovo nám 2a, 662 95 Brno, Czech Republic; polak@math.muni.cz

Published online: 3 June 2008

Abstract
A language $L\subseteq A^*$ is literally idempotent in case that $ua^2v\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\dots B^*_k$ where $B_1,\dots,B_k$ are subsets of a given alphabet A.

Mathematics Subject Classification. 68Q45

Key words: Literally idempotent languages -- varieties of languages.

© EDP Sciences 2008