×

Antisquares and critical exponents. (English) Zbl 07908410

Summary: The (bitwise) complement \(\overline{x}\) of a binary word \(x\) is obtained by changing each \(0\) in \(x\) to \(1\) and vice versa. An antisquare is a nonempty word of the form \(x \overline{x}\). In this paper, we study infinite binary words that do not contain arbitrarily large antisquares. For example, we show that the repetition threshold for the language of infinite binary words containing exactly two distinct antisquares is \((5+\sqrt{5})/2\). We also study repetition thresholds for related classes, where “two” in the previous sentence is replaced by a larger number. We say a binary word is good if the only antisquares it contains are \(01\) and \(10\). We characterize the minimal antisquares, that is, those words that are antisquares but all proper factors are good. We determine the growth rate of the number of good words of length \(n\) and determine the repetition threshold between polynomial and exponential growth for the number of good words.

MSC:

68Rxx Discrete mathematics in relation to computer science

Software:

Walnut

References:

[1] G. Badkobeh and M. Crochemore. Finite-repetition threshold for infinite ternary words. In P. Ambrož, Š. Holub, and Z. Masáková, editors, WORDS 2011, volume 63 of Elec. Proc. Theor. Comput. Sci., pages 37-43. Open Publishing Association, 2011. · Zbl 1331.68160
[2] A. Carpi and A. d. Luca. Special factors, periodicity, and an application to Sturmian words. Acta Infor-matica, 36:983-1006, 2000. · Zbl 0956.68119
[3] J. Currie and N. Rampersad. A proof of Dejean’s conjecture. Math. Comp., 80:1063-1070, 2011. · Zbl 1215.68192
[4] J. Currie, F. Manea, and D. Nowotka. Unary patterns with permutations. In I. Potapov, editor, DLT 2015, volume 9168 of Lecture Notes in Computer Science, pages 191-202. Springer-Verlag, 2015. · Zbl 1434.68383
[5] J. Currie, L. Dvořaková, D. Opočenská, N. Rampersad, and J. Shallit. Complement avoidance in binary words. Arxiv preprint arXiv:2209.09598 [math.CO]. Available at https://arxiv.org/abs/ 2209.09598, 2023.
[6] J. D. Currie, L. Mol, and N. Rampersad. The repetition threshold for binary rich words. Discrete Math. & Theoret. Comput. Sci., 22(1):DMTCS-22-1-6, 2020. URL https://dmtcs.episciences. org/6082. · Zbl 1456.68135
[7] F. Dejean. Sur un théorème de Thue. J. Combin. Theory. Ser. A, 13:90-99, 1972. · Zbl 0245.20052
[8] L. Dvořáková, K. Medková, and E. Pelantová. Complementary symmetric Rote sequences: the critical exponent and the recurrence function. Discrete Math. & Theoret. Comput. Sci., 22(1):DMTCS-22-1-20, 2020. URL https://dmtcs.episciences.org/6519/. · Zbl 1478.68269
[9] L. Dvořáková, D. Opočenská, E. Pelantová, and A. M. Shur. On minimal critical exponent of bal-anced sequences. Preprint, available at https://papers.ssrn.com/sol3/papers.cfm? abstract_id=4011686, 2022.
[10] F. Fiorenzi, P. Ochem, and E. Vaslet. Bounds for the generalized repetition threshold. Theoret. Comput. Sci., 412:2955-2963, 2011. · Zbl 1232.68097
[11] P. Hieronymi, D. Ma, R. Oei, L. Schaeffer, C. Schulz, and J. Shallit. Decidability for Sturmian words. In F. Manea and A. Simpson, editors, 30th EACSL Annual Conference on Computer Science Logic (CSL 2022), Leibniz International Proceedings in Informatics, pages 24:1-24:23. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022. · Zbl 1541.68304
[12] L. Ilie, P. Ochem, and J. Shallit. A generalization of repetition threshold. Theoret. Comput. Sci., 345: 359-369, 2005. · Zbl 1079.68082
[13] J. Karhumäki and J. Shallit. Polynomial versus exponential growth in repetition-free binary words. J. Combin. Theory. Ser. A, 105(2):335-347, 2004. · Zbl 1065.68080
[14] F. Mignosi, A. Restivo, and M. Sciortino. Words and forbidden factors. Theoret. Comput. Sci., 273: 99-117, 2002. · Zbl 0997.68093
[15] L. Mol, N. Rampersad, and J. Shallit. Extremal overlap-free and extremal β-free binary words. Electronic J. Combinatorics, 27(4):#P4.42, 2020. · Zbl 1462.68151
[16] H. Mousavi. Automatic theorem proving in Walnut. Arxiv preprint arXiv:1603.06017 [cs.FL], available at http://arxiv.org/abs/1603.06017, 2016.
[17] H. Mousavi and J. Shallit. Repetition avoidance in circular factors. In M.-P. Béal and O. Carton, editors, DLT 2013, volume 7907 of Lecture Notes in Computer Science, pages 384-395. Springer-Verlag, 2013. · Zbl 1381.68236
[18] H. Mousavi, L. Schaeffer, and J. Shallit. Decision algorithms for Fibonacci-automatic words, I: Basic results. RAIRO Inform. Théor. App., 50:39-66, 2016. · Zbl 1366.68226
[19] T. Ng, P. Ochem, N. Rampersad, and J. Shallit. New results on pseudosquare avoidance. In R. Mercas and D. Reidenbach, editors, WORDS 2019, volume 11682 of Lecture Notes in Computer Science, pages 264-274. Springer-Verlag, 2019. · Zbl 1444.68154
[20] N. Rampersad, J. Shallit, and É. Vandomme. Critical exponents of infinite balanced words. Theoret. Comput. Sci., 777:454-463, 2019. · Zbl 1446.68132
[21] M. Rao. Last cases of Dejean’s conjecture. Theoret. Comput. Sci., 412:3010-3018, 2011. · Zbl 1230.68163
[22] A. V. Samsonov and A. M. Shur. On Abelian repetition threshold. RAIRO Inform. Théor. App., 46: 147-163, 2012. · Zbl 1279.68240
[23] J. Shallit. Simultaneous avoidance of large squares and fractional powers in infinite binary words. Internat. J. Found. Comp. Sci., 15:317-327, 2004. · Zbl 1067.68119
[24] J. Shallit. Minimal critical exponents for palindromes. ArXiv preprint, arXiv:1612.05320 [cs.FL]. Avail-able at https://arxiv.org/abs/1612.05320, 2016.
[25] J. Shallit. The Logical Approach To Automatic Sequences: Exploring Combinatorics on Words with Walnut, volume 482 of London Math. Soc. Lecture Note Series. Cambridge University Press, 2022.
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.