Pattern avoidance in partial words over a ternary alphabet (Q2517160): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1155495284 / rank | |||
Normal rank |
Revision as of 21:12, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Pattern avoidance in partial words over a ternary alphabet |
scientific article |
Statements
Pattern avoidance in partial words over a ternary alphabet (English)
0 references
17 August 2015
0 references
A long-standing conjecture from [\textit{J. Cassaigne}, Motifs évitables et régularités dans les mots. Paris: Université Paris VI (PhD Thesis) (1994)] states that for a pattern \(p\) with exactly \(k\) distinct variables, (1) if \(p\) is of length at least \(2^k\), then its avoidability index is at most 3, while (2) if \(p\) is of length at least \(3 \cdot 2^{k-1}\), its avoidability index is 2. This conjecture was recently settled independently by \textit{F. Blanchet-Sadri} and \textit{B. Woodhouse} [Theor. Comput. Sci. 506, 17--28 (2013; Zbl 1301.68209)] and by \textit{P. Ochem} and \textit{A. Pinlou} [Electron. J. Comb. 21, No. 2, Research Paper P2.7, 12 p. (2014; Zbl 1299.68046)]. Furthermore, Blanchet-Sadri and Woodhouse conjectured that (1) is true for doubled patterns with \(k \geq 4\) distinct variables when partial word avoidability is concerned. In this paper, the authors answer affirmatively this conjecture on partial words via entropy compression and the probabilistic method.
0 references
formal languages
0 references
combinatorics on words
0 references
pattern avoidance
0 references
partial words
0 references
entropy compression
0 references
probabilistic method
0 references