Fibonacci word patterns in two-way infinite Fibonacci words. (English) Zbl 1245.68150
Summary: The studies of 1-Fibonacci word patterns and 0-Fibonacci word patterns were initiated by J. C. Turner [Fibonacci Q. 26, No. 3, 233–246 (1988; Zbl 0692.05009)] and W. Chuan [in: Applications of Fibonacci numbers. Volume 5: Proceedings of the fifth international conference on Fibonacci numbers and their applications, University of St. Andrews, Scotland, July 20-24, 1992. Dordrecht: Kluwer Academic Publishers. 113–122 (1993; Zbl 0804.11013)] respectively. It is known that each proper suffix of the infinite Fibonacci word is an \(r\)-Fibonacci word pattern, \(r \in \{0,1\}\).
In this paper, we consider the suffixes of the two two-way infinite extensions \(G\) and \(G'\) of the infinite Fibonacci word. We obtain necessary and sufficient conditions for suffixes of \(G\) and \(G'\) to be \(r\)-Fibonacci word patterns. This gives us all the mechanical words with slope \(\frac{\sqrt 5 -1}{2}\) which are \(r\)-Fibonacci word patterns. All possible \(r\)-seed words of each of them are determined. Finally, images of suffixes of \(G\) and \(G'\) under the action of certain Sturmian morphisms are computed.
In this paper, we consider the suffixes of the two two-way infinite extensions \(G\) and \(G'\) of the infinite Fibonacci word. We obtain necessary and sufficient conditions for suffixes of \(G\) and \(G'\) to be \(r\)-Fibonacci word patterns. This gives us all the mechanical words with slope \(\frac{\sqrt 5 -1}{2}\) which are \(r\)-Fibonacci word patterns. All possible \(r\)-seed words of each of them are determined. Finally, images of suffixes of \(G\) and \(G'\) under the action of certain Sturmian morphisms are computed.
MSC:
| 68R15 | Combinatorics on words |
| 11B39 | Fibonacci and Lucas numbers and polynomials and generalizations |
| 11B83 | Special sequences and polynomials |
Keywords:
two-way infinite Fibonacci word; \(r\)-Fibonacci word pattern; seed word; mechanical word; label of Fibonacci word; Sturmian morphismReferences:
| [1] | Chuan, W.-F., Fibonacci words, Fibonacci Quart., 30.1, 68-76 (1992) · Zbl 0758.68052 |
| [2] | Chuan, W.-F., Embedding Fibonacci words into Fibonacci word patterns, (Bergum, G. E.; Philippou, A. N.; Horadam, A. F., Applications of Fibonacci Numbers, Vol. 5 (1993), Kluwer Acad. Publ.: Kluwer Acad. Publ. Dordrecht, The Netherlands), 113-122 · Zbl 0804.11013 |
| [3] | Chuan, W.-F., Generating Fibonacci words, Fibonacci Quart., 33.2, 104-120 (1995) · Zbl 0846.68081 |
| [4] | Chuan, W.-F., Extraction property of the golden sequence, Fibonacci Quart., 33.2, 113-122 (1995) · Zbl 0842.11007 |
| [5] | Chuan, W.-F., Subwords of the golden sequence and the Fibonacci words, (Bergum, G. E.; Philippou, A. N.; Horadam, A. F., Applications of Fibonacci Numbers, Vol. 6 (1996), Kluwer Acad. Publ.: Kluwer Acad. Publ. Dordrecht, The Netherlands), 73-84 · Zbl 0862.11015 |
| [6] | Chuan, W.-F., \( \alpha \)-words and factors of characteristic sequences, Discrete Math., 177, 33-50 (1997) · Zbl 0890.68108 |
| [7] | Chuan, W.-F., A representation theorem of the suffixes of characteristic sequences, Discrete Appl. Math., 85, 47-57 (1998) · Zbl 0901.68156 |
| [8] | Chuan, W.-F., Sturmian morphisms and \(\alpha \)-words, Theoret. Comput. Sci., 225, 129-148 (1999) · Zbl 0930.68117 |
| [9] | Chuan, W.-F.; Chang, C.-H.; Chang, Y.-L., Suffixes of Fibonacci word patterns, Fibonacci Quart., 38.5, 432-438 (2000) · Zbl 0964.11008 |
| [10] | Chuan, W.-F.; Chen, C.-Y.; Ho, H.-L.; Liao, F.-Y., \( \alpha \)-words and the radix order, Theoret. Comput. Sci., 412, 876-891 (2011) · Zbl 1211.68296 |
| [11] | Chuan, W.-F.; Ho, H.-L., Locating factors of the infinite Fibonacci word, Theoret. Comput. Sci., 349, 429-442 (2005) · Zbl 1181.68180 |
| [12] | Chuan, W.-F.; Ho, H.-L., Factors of characteristic words: Location and decompositions, Theoret. Comput. Sci., 411, 2827-2846 (2010) · Zbl 1195.68075 |
| [13] | W.-F. Chuan, H.-L. Ho, Locating factors of a characteristic word via the Zeckendorf representation of numbers, Theoret. Comput. Sci., revised.; W.-F. Chuan, H.-L. Ho, Locating factors of a characteristic word via the Zeckendorf representation of numbers, Theoret. Comput. Sci., revised. · Zbl 1278.68236 |
| [14] | de Luca, A., A division property of the Fibonacci word, Inform. Process Lett., 54, 307-312 (1995) · Zbl 0875.68717 |
| [15] | Hendel, R. J.; Monteferrante, S. A., Hofstadter’s extraction conjecture, Fibonacci Quart., 32, 98-107 (1994) · Zbl 1233.11028 |
| [16] | Lothaire, M., Algebraic Combinatorics on Words (2002), Cambridge Univ. Press, (Chapter 2) · Zbl 1001.68093 |
| [17] | Mignosi, F., Infinite words with linear subword complexity, Theoret. Comput. Sci., 65, 221-242 (1989) · Zbl 0682.68083 |
| [18] | Turner, J. C., Fibonacci word patterns and binary sequences, Fibonacci Quart., 26.3, 233-246 (1988) · Zbl 0692.05009 |
| [19] | Venkov, B. A., Elementary Number Theory (1970), Wolters-Noordhoff: Wolters-Noordhoff Groningen, Translated from Russian and edited by H. Alderson · Zbl 0204.37101 |
| [20] | Wen, Z.-X.; Wen, Z.-Y., Some properties of the singular words of the Fibonacci word, European J. Combin., 15, 587-598 (1994) · Zbl 0823.68087 |
| [21] | Wen, Z.-X.; Wen, Z.-Y., Some properties of the factors of Sturmian sequences, Theoret. Comput. Sci., 304, 365-385 (2003) · Zbl 1045.68109 |
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.
