Some algorithms on the star operation applied to finite languages (Q794778)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Some algorithms on the star operation applied to finite languages |
scientific article |
Statements
Some algorithms on the star operation applied to finite languages (English)
0 references
1984
0 references
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.
0 references
free monoid
0 references
free semigroup
0 references
infinite sequence of languages
0 references
directed graph
0 references
finite language
0 references
C-loops
0 references
synchronizing codes
0 references