|
Journal of Automata, Languages and Combinatorics
formerly:
Journal of Information Processing and Cybernetics /
Elektronische Informationsverarbeitung und Kybernetik
|
|
@article{jalc040404,
author = {Shyr, Huei-Jan and Yu, Shyr-Shen},
title = {Some Properties of Left Non-Cancellative Languages},
journal = jalc,
year = 1999,
volume = 4,
number = 4,
pages = {351--360},
keywords = {monoid of languages, left cancellative language,
equivalence relation, regular},
abstract = {Let $X^*$ be the free monoid generated by an alphabet $X$
consisting of more than one letter. Let $X^+ = X^* \setminus
\{1\}$, where $1$ is the empty word. The family of languages
${\cal M}=\{L\mid L\subseteq X^+\ {\rm or}\ L=\{1\}\}$, is a
monoid under the catanation operation, which is known as the
monoid of languages. A language $L \in {\cal M}$ is left
cancellative if $LL_1 = LL_2$ for $L_1, L_2 \in {\cal M}$
always implies that $L_1 = L_2$. {\sc Shyr} has shown that
for a language $L$ which is left non-cancellative always
exists a word $u \in X^+$ such that $LX^+ = LX^+_u$, where
$X^+_u = X^+ \setminus \{u\}$. This paper is a study of some
algebraic properties of left non-cancellative languages. We
define for a given word $u \in X^+$, the set
${\cal L}_u = \{ L\in {\cal M} \mid LX^+ = LX^+_u \}$ and
for a left non-cancellative language $L \in {\cal M}$, the
set ${\rm Nul}(L) = \{ u \in X^+\mid LX^+ = LX^+_u \}$. We
show that ${\cal L}_u$ is a left ideal of ${\cal M}$ and
${\rm Nul}(L)$ is a right ideal of $X^*$. We give a
characterization of a language $L$ which is in ${\cal L}_u$
and a characterization of a word $u$ which is in
${\rm Nul}(L)$. A characterization of maximal null languages
is also obtained. Two languages $L_1$ and $L_2$ in ${\cal M}$
are said to be null-equivalent if
${\rm Nul}(L_1)={\rm Nul}(L_2)$. The null-equivalent relation
is an equivalence relation defined on ${\cal M}$ which is not
a left congruence relation and also not a right congruence
relation. A characterlization of two languages being
null-equivalent is obtained.}
}