부산대학교 도서관

Let $X$ be a finite nonempty alphabet, $X^\ast$ the free monoid generated by $X$ and $X^+=X^\ast\smallsetminus\{1\}$. A language $L$ over $X$ is any subset of $X^\ast$. A language $A$ over $X$ is said to be $\rho$-independent, where $\rho$ is a reflexive binary relation over $X^\ast$, if $A$ is a nonempty subset of $X^+$ and for $a,b\in A$, $a\rho b$ implies $a=b$. The relation $\pi$ is defined by $x\pi y$ if and only if $x=y=1$ or $x=x_1a_1x_2a_2\cdots x_ka_kx_{k+1}$ and $y=x_1a_1^{n_1}x_2a_2^{n_2}\cdots x_ka_k^{n_k}x_{k+1}$, $x_i\in X^\ast$, $a_j\in X$, $n_i\geq 1$. The structure and properties of $\pi$-independent languages and of the related syntactic monoid are considered. Similar information is given for other relations $\pi^\ast$ and $\pi_t^\ast$, the transitive closure of $\pi^\ast$.