×

Almost periodic sequences. (English) Zbl 1044.68100

Summary: This paper studies properties of almost periodic sequences (also known as uniformly recursive).
A sequence is almost periodic if for every finite string that occurs infinitely many times in the sequence there exists a number \(m\) such that every segment of length \(m\) contains an occurrence of the word.
We study closure properties of the set of almost periodic sequences, ways to generate such sequences (including a general way), computability issues and Kolmogorov complexity of prefixes of almost periodic sequences.

MSC:

68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ershov, Yu. L., Decidability Problems and the Constructive Models (1980), Nauka: Nauka Moscow · Zbl 0495.03009
[2] Jacobs, K., Maschinenerzeugte 0-1-Folgen, Selecta Mathematica II (1970), Springer: Springer Berlin, Heidelberg, New York · Zbl 0254.28020
[3] S. Kakutani, Ergodic theory of shift transformations, Proc. V. Berkely Simp. Prob. Stat., Vol. II, part 2, 1967, p. 407-414.; S. Kakutani, Ergodic theory of shift transformations, Proc. V. Berkely Simp. Prob. Stat., Vol. II, part 2, 1967, p. 407-414. · Zbl 0217.38004
[4] Keane, M., Generalized Morse sequences, Z. Wahrseheinlichkeitstheorie verw. Geb. Bd, 22, S, 335-353 (1968) · Zbl 0162.07201
[5] R. Loos, Computing in algebraic extensions, Compting (Suppl.4) (1982) 173-187.; R. Loos, Computing in algebraic extensions, Compting (Suppl.4) (1982) 173-187. · Zbl 0576.12001
[6] Morse, M., Recurrent geodesies on a surface of negative curvature, Trans. Amer. Math. Soc., 22, 84-100 (1921) · JFM 48.0786.06
[7] Morse, M.; Hedlund, G. A., Symbolic dynamics I, Amer. J. Math, 60, 815-866 (1938) · JFM 64.0798.04
[8] Morse, M.; Hedlund, G. A., Symbolic dynamics II — Sturmian trajectories, Amer. J. Math, 62, 1-42 (1940) · JFM 66.0188.03
[9] Semenov, A. L., Logic theories of unary functions over natural numbers, Izv. AN SSSR. Ser. Matem., 47, 3, 623-658 (1983), (in Russian)
[10] M. Sipser, Introduction to the Theory of Computation, PWS, Boston, Part 1, 1997, pp. 31-123.; M. Sipser, Introduction to the Theory of Computation, PWS, Boston, Part 1, 1997, pp. 31-123. · Zbl 1169.68300
[11] Tarski, A., A Decision Method for Elementary Algebra and Geometry (1951), Berkley: Berkley Los-Angeles · Zbl 0044.25102
[12] Uspensky, V. A.; Semenov, A. L.; Shen’, A. Kh., Can an individual sequence of zeroes and ones be random?, Russian Math. Surveys, 45, 1, 121-189 (1990) · Zbl 0702.03038
[13] Uspensky, V. A.; Shen, A. Kh., Relations between verieties of Kolmogorov complexities, Math. Systems Theory, 29, 271-292 (1996) · Zbl 0849.68059
[14] Van der Waerden, B. L., Algebra (1991), Springer, Verlag: Springer, Verlag Berlin
[15] Weber, A., On The valuedness of finite transducers, Acta Inform., 27, 8, 749-780 (1989) · Zbl 0672.68027
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.