Some algorithms on the star operation applied to finite languages
type: Item
instance of: scholarly article
title: Some algorithms on the star operation applied to finite languages
zbMATH Open document ID: 0541.20044
DOI: 10.1007/BF02572484
published in: Semigroup Forum
publication date: 1984-01-01T00:00:00Z
full work available at URL: https://eudml.org/doc/134650
review text: 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.
Mathematics Subject Classification ID: 20M35
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 3859415
zbMATH Keywords: free monoid
zbMATH Keywords: free semigroup
zbMATH Keywords: infinite sequence of languages
zbMATH Keywords: directed graph
zbMATH Keywords: finite language
zbMATH Keywords: C-loops
zbMATH Keywords: synchronizing codes
author: Jorge Almeida
reviewed by: S. M. Goberstein
MaRDI profile type: Publication
cites work: Q3704907
cites work: Sur le théorème du defaut
cites work: Free subsemigroups of a free semigroup
cites work: Q3853827
cites work: Q3276184
cites work: Q5328539
cites work: On finitely generated subsemigroups of a free semigroup
cites work: The Sardinas/Patterson and Levenshtein theorems
cites work: Quelques constructions et algorithmes rélatifs aux sous-monoides d'un monoide libre
cites work: Presentations et presentations simplifiables d'un monoide simplifiable
cites work: The intersection of free submonoids of a free monoid is free
description: scientific article; zbMATH DE number 3859415