A new approach to the paperfolding sequences. (English) Zbl 1459.68163
Beckmann, Arnold (ed.) et al., Evolving computability. 11th conference on computability in Europe, CiE 2015, Bucharest, Romania, June 29 – July 3, 2015. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9136, 34-43 (2015).
Summary: In this paper we show how to re-derive known results about the paperfolding sequences, and obtain new ones, using a new approach using a decision method and some machine computation. We also obtain exact expressions for the recurrence and appearance function of the paperfolding sequences, and solve an open problem of Rampersad about factors shared in common between two different paperfolding sequences.
For the entire collection see [Zbl 1314.68011].
For the entire collection see [Zbl 1314.68011].
References:
| [1] | Allouche, JP, The number of factors in a paperfolding sequence, Bull. Aust. Math. Soc., 46, 23-32 (1992) · Zbl 0753.11011 · doi:10.1017/S0004972700011655 |
| [2] | Allouche, JP; Bousquet-Mélou, M., Canonical positions for the factors in the paperfolding sequences, Theor. Comput. Sci., 129, 263-278 (1994) · Zbl 0820.11011 · doi:10.1016/0304-3975(94)90028-0 |
| [3] | Allouche, JP; Bousquet-Mélou, M., Facteurs des suites de Rudin-Shapiro généralisées, Bull. Belg. Math. Soc., 1, 145-164 (1994) · Zbl 0803.68096 |
| [4] | Allouche, JP; Rampersad, N.; Shallit, J., Periodicity, repetitions, and orbits of an automatic sequence, Theor. Comput. Sci., 410, 2795-2803 (2009) · Zbl 1173.68044 · doi:10.1016/j.tcs.2009.02.006 |
| [5] | Charlier, E.; Rampersad, N.; Shallit, J., Enumeration and decidable properties of automatic sequences, Int. J. Found. Comp. Sci., 23, 1035-1066 (2012) · Zbl 1282.68186 · doi:10.1142/S0129054112400448 |
| [6] | Cobham, A., Uniform tag sequences, Math. Syst. Theory, 6, 164-192 (1972) · Zbl 0253.02029 · doi:10.1007/BF01706087 |
| [7] | Davis, C.; Knuth, DE, Number representations and dragon curves-I, II, J. Recreat. Math., 3, 66-81, 133-149 (1970) · Zbl 1473.11066 |
| [8] | Dekking, F.M., Mendès France, M., Poorten, A.J.v.d.: Folds! Math. Intell. 4, 130-138, 173-181, 190-195 (1982). Erratum 5, 5 (1983) · Zbl 0493.10001 |
| [9] | Goč, D.; Henshall, D.; Shallit, J.; Moreira, N.; Reis, R., Automatic theorem-proving in combinatorics on words, Implementation and Application of Automata, 180-191 (2012), Heidelberg: Springer, Heidelberg · Zbl 1297.68215 · doi:10.1007/978-3-642-31606-7_16 |
| [10] | Kao, JY; Rampersad, N.; Shallit, J.; Silva, M., Words avoiding repetitions in arithmetic progressions, Theor. Comput. Sci., 391, 126-137 (2008) · Zbl 1133.68066 · doi:10.1016/j.tcs.2007.10.039 |
| [11] | Prodinger, H.; Urbanek, FJ, Infinite 0-1-sequences without long adjacent identical blocks, Discrete Math., 28, 277-289 (1979) · Zbl 0421.05007 · doi:10.1016/0012-365X(79)90135-3 |
| [12] | Schaeffer, L.: Deciding properties of automatic sequences. Master’s thesis, University of Waterloo, School of Computer Science (2013) |
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.
