Solid codes and disjunctive domains (Q909801): Difference between revisions

Let X be an alphabet, \(| X| >1\), \(X=\{a,b,...\}\), and let L be a language over X. L is said to be (right) disjunctive if the principal (right) congruence \(P_ L\) \((R_ L)\) is the equality on the free monoid \(X^*\) generated by X. L is a (right) disjunctive domain if the following property holds: For all \(A\subseteq X^*\), if \(\neg xP_ Ay\) \((\neg xR_ Ay)\) for all \(x,y\in L\), \(x\neq y\), then A is (right) disjunctive. Intuitively speaking, a (right) disjunctive domain is a ``test set'' for (right) disjunctivity. L is said to be a solid code if every word \(w\in X^+\) has a unique factorization of the form \(w=x_ 1y_ 1x_ 2y_ 2...x_ ny_ nx_{n+1}\) where \(y_ 1,y_ 2,...,y_ n\in L\) and \(x_ 1,x_ 2,...,x_{n+1}\not\in X^*LX^*.\) Several properties of solid codes and (right) disjunctive domains are derived in this paper. The connection between these topics arises from the following auxiliary notion which deserves investigation in its own right: Let \(u,v,w_ 1,w_ 2\in X^+\); \((w_ 1,w_ 2)\) is said to be a (u,v)-related pair if \(w_ 1=x_ 1y_ 1x_ 2y_ 2...x_ ny_ nx_{n+1}\) and \(w_ 2=x_ 1y_ 1'x_ 2y_ 2'...x_ ny_ n'x_{n+1}\) for some \(y_ 1,...,y_ n,y_ 1',...,y_ n'\in \{u,v\}\) and \(x_ 1,...,x_{n+1}\not\in X^*\{u,v\}X^*.\) The results of this paper include the following: (1) L with \(| L| >2\) is a solid code if and only if for any \(u,v\in L\) (not necessarily disctinct) to proper prefix of u is a proper suffix of v and \(u\in X^*vX^*\) only if \(u=v\). This property actually turns out to characterize solid codes in general as shown by \textit{S. S. Yu} and the reviewer [Solid codes (to appear)]. (2) L is a disjunctive domain if and only if for every \(u,v\in X^*\), \(u\neq v\), there is a (u,v)-related pair \((z,z')\) such that \(z,z'\in L\), \(z\neq z'\). Moreover, this holds also true if one considers only pairs (u,v) which satisfy the following three conditions: \(| u| =| v| \geq 3\); \(u,v\in aX^+b\setminus (a^+b\cup ab^+)\); \(\{\) u,v\(\}\) is a solid code. (3) (Right) disjunctive domains are (right) dense, that is, have a nonempty intersection with every principal (right) ideal of \(X^*\). (4) L is a right disjunctive domain if and only if for any \(u,v\in X^*\) there is a word \(x\in X^*\) such that ux,vx\(\in L\). Further results concern closure properties and combinatorial properties of (right) disjunctive domains.