LIPIcs.STACS.2017.19.pdf
- Filesize: 0.51 MB
- 13 pages
Document
On Long Words Avoiding Zimin Patterns
Authors
-
Part of:
Volume:
34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2017-03-06
Cite AsGet BibTex
Arnaud Carayol and Stefan Göller. On Long Words Avoiding Zimin Patterns. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 19:1-19:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.STACS.2017.19
https://doi.org/10.4230/LIPIcs.STACS.2017.19
Abstract
A pattern is encountered in a word if some infix of the word is the image of the pattern under some non-erasing morphism. A pattern p is unavoidable if, over every finite alphabet, every sufficiently long word encounters p. A theorem by Zimin and independently by Bean, Ehrenfeucht and McNulty states that a pattern over n distinct variables is unavoidable if, and only if, p itself is encountered in the n-th Zimin pattern. Given an alphabet size k, we study the minimal length f(n,k) such that every word of length f(n,k) encounters the n-th Zimin pattern. It is known that f is upper-bounded by a tower of exponentials. Our main result states that f(n,k) is lower-bounded by a tower of n-3 exponentials, even for k=2. To the best of our knowledge, this improves upon a previously best-known doubly-exponential lower bound. As a further result, we prove a doubly-exponential upper bound for encountering Zimin patterns in the abelian sense.
Keywords
- Unavoidable patterns
- combinatorics on words
- lower bounds
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
N. Alon and J. Spencer. The Probabilistic Method. Wiley, 2015.
- J. Cooper and D. Rorabaugh. Bounds on Zimin word avoidance. CoRR, abs/1409.3080, 2014. URL: http://arxiv.org/abs/1409.3080.
- J. Cooper and D. Rorabaugh. Asymptotic density of Zimin words. Discrete Mathematics &Theoretical Computer Science, Vol. 18, no 3, 2016. URL: http://dmtcs.episciences.org/1414.
- J. D. Currie. Pattern avoidance: themes and variations. Theor. Comput. Sci., 339(1):7-18, 2005. URL: http://dx.doi.org/10.1016/j.tcs.2005.01.004.
- J. D. Currie and V. Linek. Avoiding patterns in the abelian sense. Canadian J. Math., 51(4):696-714, 2001. URL: http://dx.doi.org/10.4153/cjm-2001-028-4.
- G. F. McNulty D. R. Bean, A. Ehrenfeucht. Avoidable Patterns in Strings of Symbols. Pac. J. of Math., 85:261-294, 1979. URL: http://dx.doi.org/10.2140/pjm.1979.85.261.
-
P. Flajolet and R. Sedgewick. Analytic combinatorics. Cambridge University Press, Cambridge, 2009.
- P. Jancar. Equivalences of pushdown systems are hard. In Proceedings of FOSSACS 2014, volume 8412 of Lecture Notes in Computer Science, pages 1-28. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-642-54830-7_1.
- V. Jugé. Abelian Ramsey length and asymptotic lower bounds. CoRR, abs/1609.06057, 2016. URL: http://arxiv.org/abs/1609.06057.
- K. Reinhardt. The complexity of translating logic to finite automata. In Automata, Logics, and Infinite Games: A Guide to Current Research, volume 2500 of Lecture Notes in Computer Science, pages 231-238. Springer, 2001. URL: http://dx.doi.org/10.1007/3-540-36387-4_13.
- D. Rorabaugh. Toward the combinatorial limit theory of free words. CoRR, abs/1509.04372, 2015. URL: http://arxiv.org/abs/1509.04372.
- W. Rytter and A. M. Shur. Searching for Zimin patterns. Theor. Comput. Sci., 571:50-57, 2015. URL: http://dx.doi.org/10.1016/j.tcs.2015.01.004.
-
M. V. Sapir. Combinatorics on words with applications. Technical report, LITP, 1995.
- S. Schmitz. Complexity hierarchies beyond elementary. CoRR, abs/1312.5686, 2014. URL: http://arxiv.org/abs/1312.5686.
- G. Sénizergues. The equivalence problem for t-turn DPDA is co-NP. Technical Report 1297-03, LaBRI, 2003. available at URL: http://dept-info.labri.u-bordeaux.fr/~ges.
- C. Stirling. Deciding DPDA equivalence is primitive recursive. In In Proceedings of ICALP 2002, volume 2380 of Lecture Notes in Computer Science, pages 821-832. Springer, 2002. URL: http://dx.doi.org/10.1007/3-540-45465-9_70.
-
L. J. Stockmeyer. The complexity of decision problems in automata and logic. PhD thesis, Massachusetts Institute of Technology, Cambridge, MA, 1974.
- J. Tao. Pattern occurrence statistics and applications to the ramsey theory of unavoidable patterns. CoRR, abs/1406.0450, 2014. URL: http://arxiv.org/abs/1406.0450.
-
A. Thue. Über unendliche Zeichenreihen. Norske Vid. Skrifter I Mat.-Nat. Kl. Christiania, 7:1 - 22, 1906.
- A. I. Zimin. Blocking sets of terms. Math. USSR Sbornik, 47:50-57, 1984. URL: http://dx.doi.org/10.1070/sm1984v047n02abeh002647.