On varieties of literally idempotent languages
| Authors | |
|---|---|
| Year of publication | 2008 |
| Type | Article in Periodical |
| Magazine / Source | RAIRO - Theoretical Informatics and Applications |
| MU Faculty or unit | |
| Citation | |
| Field | Information theory |
| Keywords | literal idempotence; varieties of languages |
| Description | 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$. Such classes 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 their systematic study. Various classes of such 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$. |
| Related projects: |