On the decomposition of prefix codes (Q517038)

The paper deals with the decomposition of rational and maximal prefix codes. A set \(X \subset A^*\) is said to be \textit{rational} if it is accepted by a finite automaton. It is a \textit{code} if it is uniquely decodable, that is, if for all \(h,k \geq 0\) and \(c_1, c_2, \ldots, c_h, \, c_1', c_2', \ldots, c_k' \in X\) one has \[ c_1 c_2 \cdots c_h = c_1' c_2' \cdots c_k' \quad \Rightarrow \quad h=k \quad \text{and} \quad c_i = c_i' \; \text{ for } \; i = 1,2, \ldots, h. \] A \textit{prefix code} is a code such that none of its elements is a prefix (i.e., a left factor) of another. A \textit{suffix code} is defined symmetrically and a \textit{bifix code} is a set of words that is both a prefix and a suffix code. A code (resp. prefix code, resp. bifix code) \(X\) is \textit{maximal} over \(A\) if it is not properly contained in any other code (resp. prefix code, resp. bifix code) over \(A\). Composition is a partially binary operation on codes. Given two codes \(Z \subseteq A^*\) and \(Y \subset B^*\) such that each letter \(b \in B\) is a factor of at least one word in \(Y\), we say that \(Y\) and \(Z\) are \textit{composable} if there is a bijection \(\beta\) from \(B\) onto \(Z\). The code \(X = \beta(Y) \subseteq Z^*\), denoted by \(X = Y \circ Z\) is said to be obtained by \textit{composition} of \(Y\) and \(Z\). Roughly speaking, the words in \(X\) are obtained by the ones in \(Y\) just by replacing each letter \(b \in B\) by the word \(\beta(b) \in Z\). A code \(X \subset A^+\) is \textit{indecomposable} if, whenever \(X = Y \circ Z\), then either \(Z=A\) or \(Y=B\). Otherwise we say that \(X\) \textit{decomposes} or that it is \textit{decomposable} over \(Z\). If a code \(X\) decomposes over two codes \(Y\) and \(Z\), then these codes are generally simpler. It is not known if it is decidable whether a rational maximal prefix code decomposes over a finite prefix code. The approach used in this paper takes into account the minimal automaton \(\mathcal{A} = (Q,1,1)\) recognizing \(X^*\), where \(X\) is a rational maximal prefix code. The authors introduce the definitions of \textit{balanced} state and of \textit{unbalanced} state. They present an effective procedure that can decide whether a rational and maximal prefix code \(X\) is decomposable. In this case, the procedure also produces the factors of some decomposition of \(X\). Two extremal classes of rational maximal prefix codes are studied: the class of \textit{balanced codes}, when all states different from \(1\) are balanced, and the one of \textit{strongly unbalanced codes}, when all states different from \(1\) are unbalanced. The former is a rather large class, including rational maximal bifix codes and indecomposable rational maximal prefix codes. The latter coincides with the class of \((1,0)\)\textit{-limited codes}. Moreover, several partial results are given on the problem of deciding whether a rational maximal prefix code decomposes over a finite prefix code. In particular, it is shown that it is possible to decide whether a rational and maximal bifix code decomposes over a finite bifix maximal code and that any strongly unbalanced code decomposes over a finite maximal prefix code.