×

Unavoidable set: Extension and reduction. (English) Zbl 0941.68104

Summary: We give an explicit criterion for unavoidability of word sets. We characterize extendible, finitely and infinitely as well, elements in them. We furnish a reasonable upper bound and an exponential lower bound on the maximum length of words in a reduced unavoidable set of a given cardinality.

MSC:

68R15 Combinatorics on words
68T50 Natural language processing

Keywords:

word sets
PDFBibTeX XMLCite
Full Text: DOI Numdam EuDML

References:

[1] M.-P. Schützenberger, On the Synchronizing Properties of Certain Prefix Codes. Inform. and Control7 (1964) 23-36. · Zbl 0122.15004 · doi:10.1016/S0019-9958(64)90232-3
[2] A.V. Aho and M.J. Corasick, Efficient String Machines, an Aid to Bibliographic Research. Comm. ACM18 (1975) 333-340. · Zbl 0301.68048 · doi:10.1145/360825.360855
[3] A. Ehrenfeucht, D. Haussler and G. Rozengerg, On Regularity of Context-free Languages. Theoret. Comput. Sci.27 (1983) 311-332. · Zbl 0553.68044 · doi:10.1016/0304-3975(82)90124-4
[4] Ch. Choffrut and K. CulikII, On Extendibility of Unavoidable Sets. Discrete Appl. Math.9 (1984) 125-137. · Zbl 0629.68080 · doi:10.1016/0166-218X(84)90014-3
[5] L. Rosaz, Inventories of Unavoidable Languages and the Word-Extension Conjecture, to appear. · Zbl 0902.68099 · doi:10.1016/S0304-3975(97)00031-5
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.