{"@context":["https://w3id.org/fdo/context/v1",{"schema":"https://schema.org/","prov":"http://www.w3.org/ns/prov#","fdo":"https://w3id.org/fdo/vocabulary/"}],"@id":"https://fdo.portal.mardi4nfdi.de/fdo/Q1107641","@type":"DigitalObject","kernel":{"@id":"https://fdo.portal.mardi4nfdi.de/fdo/Q1107641","digitalObjectType":"https://schema.org/ScholarlyArticle","primaryIdentifier":"mardi:Q1107641","kernelVersion":"v1","immutable":true,"modified":"2026-01-06T18:18:11Z"},"profile":{"@context":"https://schema.org","@type":"ScholarlyArticle","@id":"https://portal.mardi4nfdi.de/entity/Q1107641","name":"An answer to a question about finite maximal prefix sets of words","headline":"An answer to a question about finite maximal prefix sets of words","description":"scientific article; zbMATH DE number 4065305","url":"https://portal.mardi4nfdi.de/entity/Q1107641","datePublished":"1988-00-00","author":[{"@id":"https://portal.mardi4nfdi.de/entity/Q213200"}],"publisher":[{"@id":"https://portal.mardi4nfdi.de/entity/Q123643"}],"identifier":{"@type":"PropertyValue","propertyID":"doi","value":"10.1016/0304-3975(88)90139-9","url":"https://doi.org/10.1016/0304-3975(88)90139-9"},"sameAs":["https://doi.org/10.1016/0304-3975(88)90139-9"],"comment":"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.","citation":[{"@id":"https://portal.mardi4nfdi.de/entity/Q4430300"},{"@id":"https://portal.mardi4nfdi.de/entity/Q1821877"},{"@id":"https://portal.mardi4nfdi.de/entity/Q5527869"},{"@id":"https://portal.mardi4nfdi.de/entity/Q5540495"}]},"provenance":{"prov:generatedAtTime":"2026-01-06T18:18:11Z","prov:wasAttributedTo":"MaRDI Knowledge Graph"}}