An answer to a question about finite maximal prefix sets of words
type: Item
instance of: scholarly article
title: An answer to a question about finite maximal prefix sets of words
zbMATH Open document ID: 0653.20061
DOI: 10.1016/0304-3975(88)90139-9
author: Véronique Bruyère
published in: Theoretical Computer Science
publication date: 1988-01-01T00:00:00Z
review text: A set X of words over a finite alphabet is said to be prefix if no element of X is a proper left factor of another element of X. The concatenation product XY of two sets of words X and Y is unambiguous if each \(w\in XY\) admits a unique factorization \(w=xy\) with \(x\in X\) and \(y\in Y\). The concatenation product of two maximal prefix sets is itself maximal prefix. Conversely, \textit{M. P. Schützenberger} proved that, if XY is a finite maximal prefix unambiguous product, then X and Y are maximal prefix sets [Bull. Soc. Math. Fr. 93, 209-223 (1965; Zbl 0149.026)]. It is easy to provide counter-examples if the finiteness hypothesis on XY is dropped. The question addressed by the author is whether the unambiguity hypothesis is also essential. She exhibits an example of a finite maximal prefix product XY over a two-letter alphabet where: a) X is a set with three elements which is not prefix and b) Y is a prefix set for which the smallest prefix set containing it has another 7 elements. Based on techniques and results developed in another paper [Semigroup Forum 36, 147-157 (1987; Zbl 0617.20041)], she also shows that, in a certain sense, her example is minimal.
Mathematics Subject Classification ID: 20M05
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 20M35
zbMATH DE Number: 4065305
zbMATH Keywords: subsets of free semigroups
zbMATH Keywords: concatenation product
zbMATH Keywords: maximal prefix sets
zbMATH Keywords: unambiguous product
zbMATH Keywords: finite maximal prefix product
reviewed by: Jorge Almeida
MaRDI profile type: Publication
full work available at URL: 0304-3975(88)90139-9
OpenAlex ID: W2031772228
cites work: Q4430300
cites work: Maximal prefix products
cites work: Sur certains sous-monoïdes libres
cites work: On a question concerning certain free submonoids
description: scientific article; zbMATH DE number 4065305