×

On avoidability of formulas with reversal. (English) Zbl 1390.68512

Summary: While a characterization of unavoidable formulas (without reversal) is well-known, little is known about the avoidability of formulas with reversal in general. In this article, we characterize the unavoidable formulas with reversal that have at most two one-way variables (\( x\) is a one-way variable in formula with reversal \(\phi\) if exactly one of \( x\) and \(x^R\) appears in \(\phi\)).

MSC:

68R15 Combinatorics on words
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] D.R. Bean, A. Ehrenfeucht and G.F. McNulty, Avoidable patterns in strings of symbols. Pac. J. Math.85 (1979) 261-294. · Zbl 0428.05001
[2] J. Cassaigne, Motifs évitables et régularité dans les mots, Ph.D. Thesis. Université Paris VI (1994).
[3] R.J. Clark, Avoidable Formulas in Combinatorics on Words, Ph.D. Thesis. University of California, Los Angeles (2001).
[4] J.D. Currie and P. Lafrance, Avoidability index for binary patterns with reversal. Electron. J. Combin.23 (2016) 1-36. · Zbl 1332.68177
[5] J.D. Currie and N. Rampersad, A proof of Dejean’s conjecture. Math. Comp.80 (2011) 1063-1070. · Zbl 1215.68192
[6] J.D. Currie, L. Mol and N. Rampersad, A family of formulas with reversahigl of h avoidability index. Int. J. Algebra Comput.27 (2017) 477. · Zbl 1378.68132
[7] M. Lothaire, Algebraic Combinatorics on Words. Cambridge University Press (2002). · Zbl 1001.68093
[8] M. Rao, Last cases of Dejean’s conjecture. Theoret. Comput. Sci.412 (2011) 3010-3018. · Zbl 1230.68163
[9] A.I. Zimin, Blocking sets of terms (English translation). Math. USSR Sbornik 47 (1984) 353-364. · Zbl 0599.20106
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.