On long words avoiding Zimin patterns

DOI10.1007/S00224-019-09914-2MaRDI QIDQ2321925zbMATH OpenOpenAlexFDO

Authors Arnaud Carayol, Stefan Göller

Publication date 27 August 2019

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2017/7014/

zbMATH Keywords

combinatorics on wordslower boundsunavoidable patternsZimin word

Mathematics Subject Classification ID

Ramsey theory (05D10) Combinatorics on words (68R15)

Review text

A word \(w\) is said to contain the pattern \(P\) if there is a way to substitute a nonempty word for each letter in \(P\) so that the resulting word is a subword of \(w\). The pattern \(P\) is called unavoidable if any sufficiently long word over a fixed alphabet contains \(P\). It is known that \(P\) is unavoidable if and only if it is contained in one of the so-called Zimin words \(Z_n\), where \(Z_1=x_1\) and \(Z_n=Z_{n-1}x_nZ_{n-1}\). Let \(f(n,k)\) be the least integer such that any word of length \(f(n,k)\) over an alphabet of size \(k\) contains \(Z_n\). It is proved that \(f(n,2n-1)>\mathrm{Tower}(n-1,2)\) and \(f(n,2)>\mathrm{Tower}(n-3,2)\). Also, some new similar estimates in the abelian version of the problem are proved.

Recommendations

• On Long Words Avoiding Zimin Patterns
• Tower-type bounds for unavoidable patterns in words
• Avoidable patterns on two letters
• Bounds on Zimin word avoidance
• Long unavoidable patterns

Cites work

• Analytic combinatorics
• Asymptotic density of Zimin words
• Avoidable patterns in strings of symbols
• Avoiding patterns in the abelian sense
• BLOCKING SETS OF TERMS
• Bounds on Zimin word avoidance
• Equivalences of Pushdown Systems Are Hard
• scientific article; zbMATH DE number 2038732 (Why is no real title available?)
• scientific article; zbMATH DE number 2086674 (Why is no real title available?)
• On Long Words Avoiding Zimin Patterns
• On long words avoiding Zimin patterns
• Pattern avoidance: themes and variations
• Searching for Zimin patterns
• Squaring transducers: An efficient procedure for deciding functionality and sequentiality.
• The Complexity of Translating Logic to Finite Automata
• The probabilistic method
• Tower-type bounds for unavoidable patterns in words

Cited in

(12)

• Long unavoidable patterns
• Defining long words succinctly in FO and MSO
• On long words avoiding Zimin patterns
• Exponential lower bounds for the number of words of uniform length avoiding a pattern
• Searching for Zimin patterns
• Asymptotic density of Zimin words
• scientific article; zbMATH DE number 3980522 (Why is no real title available?)
• Unavoidable regularities in long words with bounded number of symbol occurrences
• scientific article; zbMATH DE number 1786461 (Why is no real title available?)
• On Long Words Avoiding Zimin Patterns
• Tower-type bounds for unavoidable patterns in words
• Bounds on Zimin word avoidance

This page was built for publication: On long words avoiding Zimin patterns

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