Maximal prefix products

DOI10.1007/BF02575011MaRDI QIDQ1821877zbMATH OpenOpenAlexFDO

Authors Véronique Bruyère

Publication date 1987

Published in Semigroup Forum (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/134891

zbMATH Keywords

ambiguous productmaximal prefix codesunambiguouswords

Mathematics Subject Classification ID

Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35) Formal languages and automata (68Q45)

Review text

M. P. Schützenberger has proved that two finite subsets of words the product of which is a maximal prefix code, are also maximal prefix codes, provided this product is finite and unambiguous. The finiteness condition is necessary, however, this question is unsolved for the unambiguity hypothesis. We show in four particular cases that a product of two subsets of words which forms a finite maximal prefix code, is necessarily unambiguous. Remark: After the submission of the paper, we pursued the study of the problem and we were able to give a complete answer to the open problem, by constructing an example of a finite maximal prefix and ambiguous product of which the two factors are not maximal prefix codes [submitted to Theor. Comput. Sci.].

Recommendations

• scientific article; zbMATH DE number 4060747
• An answer to a question about finite maximal prefix sets of words
• About prefix sets of words
• Product of Finite Maximal P-Codes. This paper was supported in part by HK UGC grants 9040596, 9040511 and City U Strategic Grants 7001189, 7001060, and by the Natural Science Foundation of China (project No. 60073056) and the Guangdong Provincial Natural
• Factorization of prefix-closed subsets of words

Cites work

• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• scientific article; zbMATH DE number 3943051 (Why is no real title available?)
• On a question concerning certain free submonoids
• Uniqueness Theorems for Periodic Functions

Cited in

(9)

• An answer to a question about finite maximal prefix sets of words
• About prefix sets of words
• Iterations of languages and maximal prefix codes
• Product of maximal prefix codes
• scientific article; zbMATH DE number 4145828 (Why is no real title available?)
• scientific article; zbMATH DE number 4060747 (Why is no real title available?)
• Factorisation des ensembles préfixiels
• Product of Finite Maximal P-Codes. This paper was supported in part by HK UGC grants 9040596, 9040511 and City U Strategic Grants 7001189, 7001060, and by the Natural Science Foundation of China (project No. 60073056) and the Guangdong Provincial Natural Science Foundation (project No. 001174)
• Factorization of prefix-closed subsets of words

This page was built for publication: Maximal prefix products

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1821877)