Avoidability of palindrome patterns

DOI10.37236/9593MaRDI QIDQ2223455zbMATH OpenOpenAlexFDO

Authors Pascal Ochem, Matthieu Rosenfeld

Publication date 29 January 2021

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.37236/9593

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

avoidabilityinfinite wordpalindrome

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Review text

This paper deals with the avoidability of palidrome patterns in infinite words. A pattern is a non-empty finite word over an alphabet of capital letters called variables. A pattern is said to be \(k\)-avoidable if there exists an infinite word over a \(k\)-letter alphabet that avoids it. The avoidability index of a pattern is the size of the smallest such alphabet. A formula is obtained from a pattern by replacing every isolated variable (with only one appearance) by a dot. The factors between the dots are called fragments. A palindrome pattern is equal to its mirror image. The authors ``characterize the formulas that are avoided by every \(\alpha\)-free word for some \(\alpha > 1\) and show that the avoidable formulas whose fragments are of the form \(XY\) or \(XYX\) are 4-avoidable. The largest avoidability index of an avoidable palindrome pattern is known to be at least 4 and at most 16. They ``make progress toward the conjecture that every avoidable palindrome pattern is 4-avoidable.

Recommendations

• scientific article; zbMATH DE number 4035171
• Avoidable patterns on two letters
• THE EXISTENCE OF A PATTERN WHICH IS 5-AVOIDABLE BUT 4-UNAVOIDABLE
• Avoidability of formulas with two variables
• Avoiding patterns in the abelian sense

Cites work

• A generator of morphisms for infinite words
• Application of entropy compression in pattern avoidance
• Avoidability of circular formulas
• Avoidability of formulas with two variables
• Avoidable patterns in strings of symbols
• Avoiding patterns in the abelian sense
• Characterization of some binary words with few squares
• Doubled patterns are 3-avoidable
• Growth problems for avoidable words
• On some interesting ternary formulas
• On the avoidability index of palindromes
• Substitutions in dynamics, arithmetics and combinatorics

Cited in

(17)

• Avoidability of circular formulas
• Formulas with reversal
• Doubled patterns with reversal are 3-avoidable
• Pattern avoidance by palindromes
• The undirected repetition threshold and undirected pattern avoidance
• A family of formulas with reversal of arbitrarily high avoidability index
• Doubled patterns with reversal and square-free doubled patterns
• Pattern avoidability with involution
• Pattern Avoidance and Overlap in Strings
• On the avoidability index of palindromes
• Palindrome pattern matching
• Pattern Avoidance in Reverse Double Lists
• THE EXISTENCE OF A PATTERN WHICH IS 5-AVOIDABLE BUT 4-UNAVOIDABLE
• Palindromes and primitivity
• On some interesting ternary formulas
• More characterizations of morphic words
• 4-tangrams are 4-avoidable

This page was built for publication: Avoidability of palindrome patterns

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