Ostrowski-automatic sequences: theory and applications. (English) Zbl 1467.68146
A so-called Ostrowski numeration system is defined to canonically represent integers based on the denominators of the convergents of the continued fraction of an irrational number. For instance, with the golden mean, we get back the classical Zeckendorf numeration system based on the Fibonacci sequence.
Given an irrational, the authors construct an automaton that recognizes the addition relation in such a system. In order to recognize this relation, they use an automaton that reads three integers represented in their canonical representation, along with the sequence of continued fraction, in parallel.
They discuss the implementation for quadratic irrationals which has been integrated in the automatic theorem prover Walnut. The software, based on the Büchi-Bruyère theorem and initially built for automatic sequences, is therefore extended to a wider setting. In the second part of the paper, they apply their constructions to several problems in combinatorics on words: repetitions and pattern avoidance, partial solution to a conjecture about critical exponents in balanced words and discussions about rich words and Lucas words.
Given an irrational, the authors construct an automaton that recognizes the addition relation in such a system. In order to recognize this relation, they use an automaton that reads three integers represented in their canonical representation, along with the sequence of continued fraction, in parallel.
They discuss the implementation for quadratic irrationals which has been integrated in the automatic theorem prover Walnut. The software, based on the Büchi-Bruyère theorem and initially built for automatic sequences, is therefore extended to a wider setting. In the second part of the paper, they apply their constructions to several problems in combinatorics on words: repetitions and pattern avoidance, partial solution to a conjecture about critical exponents in balanced words and discussions about rich words and Lucas words.
Reviewer: Michel Rigo (Liège)
MSC:
| 68R15 | Combinatorics on words |
| 11B85 | Automata sequences |
| 68Q45 | Formal languages and automata |
| 68V15 | Theorem proving (automated and interactive theorem provers, deduction, resolution, etc.) |
Keywords:
decision procedure; automatic sequence; Ostrowski numeration; repetition; balanced word; palindrome-rich word; Lucas wordReferences:
| [1] | Cobham, A., Uniform tag sequences, Math. Syst. Theory, 6, 164-192 (1972) · Zbl 0253.02029 |
| [2] | Allouche, J. P.; Shallit, J., Automatic Sequences—Theory, Applications, Generalizations (2003), Cambridge University Press · Zbl 1086.11015 |
| [3] | Rampersad, N.; Shallit, J.; Vandomme, E., Critical exponents of infinite balanced words, Theor. Comput. Sci., 777, 454-463 (2019) · Zbl 1446.68132 |
| [4] | Baranwal, A. R.; Shallit, J., Critical exponent of infinite balanced words via the Pell number system, (Mercaş, R.; Reidenbach, D., Combinatorics on Words (2019), Springer International Publishing: Springer International Publishing Cham), 80-92 · Zbl 1447.68009 |
| [5] | Baranwal, A. R.; Shallit, J., Repetitions in infinite palindrome-rich words, (Mercaş, R.; Reidenbach, D., Combinatorics on Words (2019), Springer International Publishing: Springer International Publishing Cham), 93-105 · Zbl 1447.68010 |
| [6] | Ostrowski, A., Bemerkungen zur Theorie der Diophantischen Approximationen, Abh. Math. Semin. Hamb., 1, 77-98 (1922), 250-251, reprinted in: Collected Mathematical Papers, vol. 3, pp. 57-80 · JFM 48.0185.01 |
| [7] | Büchi, J. R., Weak secord-order arithmetic and finite automata, Z. Math. Log. Grundl. Math.. (Mac Lane, S.; Siefkes, D., The Collected Works of J. Richard Büchi (1990), Springer-Verlag), 6, 398-424 (1960), reprinted |
| [8] | Cobham, A., On the base-dependence of sets of numbers recognizable by finite automata, Math. Syst. Theory, 3, 186-192 (1969) · Zbl 0179.02501 |
| [9] | Eilenberg, S., Automata, Languages, and Machines, Vol. A (1974), Academic Press · Zbl 0317.94045 |
| [10] | Christol, G., Ensembles presque périodiques k-reconnaissables, Theor. Comput. Sci., 9, 141-145 (1979) · Zbl 0402.68044 |
| [11] | Presburger, M.; Jacquette, D., On the completeness of a certain system of arithmetic of whole numbers in which addition occurs as the only operation, Hist. Philos. Log., 12, 2, 225-233 (1991) · Zbl 0741.03027 |
| [12] | Bruyère, V.; Hansel, G.; Michaux, C.; Villemaire, R., Logic and p-recognizable sets of integers, Bull. Belg. Math. Soc.. Bull. Belg. Math. Soc., Bull. Belg. Math. Soc., 1, 577-238 (1994), Corrigendum · Zbl 0804.11024 |
| [13] | Bruyère, V.; Hansel, G., Recognizable sets of numbers in nonstandard bases, (Baeza-Yates, R.; Goles, E.; Poblete, P. V., LATIN ’95: Theoretical Informatics. LATIN ’95: Theoretical Informatics, Lecture Notes in Computer Science, vol. 911 (1995), Springer-Verlag), 167-179 · Zbl 1510.11026 |
| [14] | Shallit, J., Decidability and enumeration for automatic sequences: a survey, (Bulatov, A. A.; Shur, A. M., Computer Science-Theory and Applications (2013), Springer: Springer Berlin Heidelberg, Berlin, Heidelberg), 49-63 · Zbl 1381.68238 |
| [15] | Mousavi, H.; Schaeffer, L.; Shallit, J., Decision algorithms for Fibonacci-automatic words, I: basic results, RAIRO Inform. Théor. Appl., 50, 1, 39-66 (2016) · Zbl 1366.68226 |
| [16] | Hieronymi, P.; Terry, A., Ostrowski numeration systems, addition, and finite automata, Notre Dame J. Form. Log., 59, 2, 215-232 (2018) · Zbl 1431.11017 |
| [17] | Frougny, C.; Solomyak, B., On representation of integers in linear numeration systems, (Pollicott, M.; Schmidt, K., Ergodic Theory of \(\mathbb{Z}^d\) Actions. Ergodic Theory of \(\mathbb{Z}^d\) Actions, Warwick, 1993-1994. Ergodic Theory of \(\mathbb{Z}^d\) Actions. Ergodic Theory of \(\mathbb{Z}^d\) Actions, Warwick, 1993-1994, London Mathematical Society Lecture Note Series, vol. 228 (1996), Cambridge University Press), 345-368 · Zbl 0856.11007 |
| [18] | Baranwal, A., Decision algorithms for Ostrowski-automatic sequences (2020), University of Waterloo, Master’s thesis |
| [19] | Mousavi, H., Automatic theorem proving in Walnut (2016), arXiv preprint |
| [20] | Hopcroft, J., An \(n \log n\) algorithm for minimizing states in a finite automaton, (Theory of Machines and Computations (1971), Elsevier), 189-196 · Zbl 0293.94022 |
| [21] | Vuillon, L., Balanced words, Bull. Belg. Math. Soc., 10, 5, 787-805 (2003) · Zbl 1070.68129 |
| [22] | Berstel, J.; Séébold, P., Sturmian words, (Lothaire, M., Algebraic Combinatorics on Words. Algebraic Combinatorics on Words, Encyclopedia of Mathematics and Its Applications, vol. 90 (2002), Cambridge University Press), 45-110 · Zbl 1001.68093 |
| [23] | Hubert, P., Suites équilibrées, Theor. Comput. Sci., 242, 91-108 (2000) · Zbl 0944.68149 |
| [24] | Du, C. F.; Mousavi, H.; Schaeffer, L.; Shallit, J., Decision algorithms for Fibonacci automatic words, III: enumeration and Abelian properties, Int. J. Found. Comput. Sci., 27, 8, 943-963 (2016) · Zbl 1366.68224 |
| [25] | Dejean, F., Sur un théorème de Thue, J. Comb. Theory, Ser. A, 13, 1, 90-99 (1972) · Zbl 0245.20052 |
| [26] | Currie, J.; Rampersad, N., A proof of Dejean’s conjecture, Math. Comput., 80, 274, 1063-1070 (2011) · Zbl 1215.68192 |
| [27] | Rao, M., Last cases of Dejean’s conjecture, Theor. Comput. Sci., 412, 27, 3010-3018 (2011) · Zbl 1230.68163 |
| [28] | Brlek, S.; Hamel, S.; Nivat, M.; Reutenauer, C., On the palindromic complexity of infinite words, Int. J. Found. Comput. Sci., 15, 293-306 (2004) · Zbl 1067.68113 |
| [29] | Luca, A.d.; Glen, A.; Zamboni, L. Q., Rich, Sturmian, and trapezoidal words, Theor. Comput. Sci., 407, 569-573 (2008) · Zbl 1153.68045 |
| [30] | Glen, A.; Justin, J.; Widmer, S.; Zamboni, L. Q., Palindromic richness, Eur. J. Comb., 30, 510-531 (2009) · Zbl 1169.68040 |
| [31] | Bucci, M.; Luca, A. D.; Glen, A.; Zamboni, L. Q., A new characteristic property of rich words, Theor. Comput. Sci., 410, 2860-2863 (2009) · Zbl 1173.68048 |
| [32] | Guo, C.; Shallit, J.; Shur, A. M., Palindromic rich words and run-length encodings, Inf. Process. Lett., 116, 735-738 (2016) · Zbl 1371.68221 |
| [33] | Vesti, J., Extensions of rich words, Theor. Comput. Sci., 548, 14-24 (2014) · Zbl 1307.68063 |
| [34] | Currie, J. D.; Mol, L.; Rampersad, N., The repetition threshold for binary rich words, Discret. Math. Theor. Comput. Sci., 22, 1 (2020) · Zbl 1456.68135 |
| [35] | Pelantová, E.; Starosta, S., Languages invariant under more symmetries: overlapping factors versus palindromic richness, Discrete Math., 313, 2432-2445 (2013) · Zbl 1279.05002 |
| [36] | Vesti, J., Rich square-free words, Theor. Comput. Sci., 687, 48-61 (2017) · Zbl 1376.68120 |
| [37] | Angluin, D., Learning regular sets from queries and counterexamples, Inf. Comput., 75, 2, 87-106 (1987) · Zbl 0636.68112 |
| [38] | Rote, G., Sequences with subword complexity 2n, J. Number Theory, 46, 196-213 (1994) · Zbl 0804.11023 |
| [39] | Blondin Massé, A.; Brlek, S.; Labbé, S.; Vuillon, L., Palindromic complexity of codings of rotations, Theor. Comput. Sci., 412, 6455-6463 (2011) · Zbl 1227.68084 |
| [40] | Pelantová, E.; Starosta, Š., Constructions of words rich in palindromes and pseudopalindromes, Discret. Math. Theor. Comput. Sci., 18 (2016), Paper #16, available at · Zbl 1401.68258 |
| [41] | Schaeffer, L.; Shallit, J., Closed, palindromic, rich, privileged, trapezoidal, and balanced words in automatic sequences, Electron. J. Comb., 23 (2016) · Zbl 1338.11039 |
| [42] | Barabash, G.; Kholyavka, Y.; Tytar, I., Periodic words connected with the Lucas numbers, 84, 62-66 (2017) |
| [43] | Lothaire, M., Algebraic Combinatorics on Words, Encyclopedia of Mathematics and Its Applications, vol. 90 (2002), Cambridge University Press · Zbl 1001.68093 |
| [44] | Pirillo, G., Fibonacci numbers and words, (Séminaire Lotharingien de Combinatoire. Séminaire Lotharingien de Combinatoire, Gerolfingen, 1993. Séminaire Lotharingien de Combinatoire. Séminaire Lotharingien de Combinatoire, Gerolfingen, 1993, Prépubl. Inst. Rech. Math. Av., vol. 34 (1993, 1993), Univ. Louis Pasteur: Univ. Louis Pasteur Strasbourg), 77-85 |
| [45] | Mousavi, H.; Shallit, J., Mechanical proofs of properties of the tribonacci word, (International Conference on Combinatorics on Words (2015), Springer), 170-190 · Zbl 1350.68218 |
| [46] | Currie, J.; Harju, T.; Ochem, P.; Rampersad, N., Some further results on squarefree arithmetic progressions in infinite words, Theor. Comput. Sci., 799, 140-148 (2019) · Zbl 1436.68276 |
| [47] | Shallit, J.; Zarifi, R., Circular critical exponents for Thue-Morse factors, RAIRO Inform. Théor. Appl., 53, 1-2, 37-49 (2019) · Zbl 1445.68185 |
| [48] | Ng, T.; Ochem, P.; Rampersad, N.; Shallit, J., New results on pseudosquare avoidance, (International Conference on Combinatorics on Words (2019), Springer), 264-274 · Zbl 1444.68154 |
| [49] | Bonardo, P.; Frid, A. E.; Shallit, J., The number of valid factorizations of Fibonacci prefixes, Theor. Comput. Sci., 775, 68-75 (2019) · Zbl 1423.68367 |
| [50] | Bell, J. P.; Lidbetter, T. F.; Shallit, J., Additive number theory via approximation by regular languages, (International Conference on Developments in Language Theory (2018), Springer), 121-132 · Zbl 1462.11014 |
| [51] | Schaeffer, L.; Shallit, J., The critical exponent is computable for automatic sequences, Int. J. Found. Comput. Sci., 23, 08, 1611-1626 (2012) · Zbl 1285.68138 |
| [52] | Rubinchik, M.; Shur, A. M., EERTREE: an efficient data structure for processing palindromes in strings, (International Workshop on Combinatorial Algorithms (2015), Springer), 321-333 · Zbl 1472.68046 |
| [53] | Chen, G.; Puglisi, S. J.; Smyth, W. F., Fast & practical algorithms for computing all the runs in a string, (Ma, B.; Zhang, K., CPM 07. CPM 07, Lecture Notes in Computer Science, vol. 4580 (2007), Springer-Verlag), 307-315 · Zbl 1138.68658 |
| [54] | Dvořáková, L.; Medková, K.; Pelantová, E., Complementary symmetric Rote sequences: the critical exponent and the recurrence function (2020), arXiv preprint · Zbl 1478.68269 |
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.
