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
    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
    0 references
    0 references
    0 references
    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
    0 references