Some algorithms on the star operation applied to finite languages (Q794778)

Let A be an alphabet. Let \(A^*\) denote the free monoid and \(A^+\) the free semigroup generated by A. A language on the alphabet A is any subset L of \(A^*\). The submonoid of \(A^*\) generated by L is denoted by \(L^*\). If L freely generates \(L^*\), then L is called a code. Given a language L, an important problem is to determine if L is a code. A necessary and sufficient condition for L to be a code was found by \textit{A. A. Sardinas} and \textit{C. W. Patterson} [A necessary and sufficient condition for unique decomposition of coded messages, in Convention Records of the I.R.E. 8, 104-108 (1953)]. That condition was formulated in terms of an infinite sequence of languages and was not very convenient to use. In Section 2 the author introduces a special directed graph for a finite language C with two types of arrows which displays the information contained in the Sardinas-Patterson sequence in a more convenient way (this is a crucial construction for the whole paper). He establishes a one-to-one correspondence between the set of all paths in that graph and the set of all so-called irreducible equalities involving elements of C (Theorem 2.3) and then gives a necessary and sufficient condition for C to be a code in terms of so-called C-loops in the graph. Let C be a finite language in \(A^+\). In Section 3 a presentation of \(C^*\) in terms of defining relations is given and in Section 4 a code F is constructed such that \(F^*\) is the smallest free submonoid of \(A^*\) containing C. In Section 5 the graph mentioned above is used for characterizing initially, finally or simply synchronizing codes. The paper under review is one of several papers based on the author's Ph. D. Thesis written at the Pennsylvania State University under the supervision of G. Lallement.