Abstract
D. Krieger and J. Shallit have proved that every real number greater than 1 is a critical exponent of some sequence [1]. We show how this result can be derived from some general statements about sequences whose subsequences have (almost) maximal Kolmogorov complexity. In this way one can also construct a sequence that has no “approximate” fractional powers with exponent that exceeds a given value.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Krieger, D., Shallit, J.: Every real number greater than 1 is a critical exponent (preprint, 2007)
Yu. Rumyantsev, A., Ushakov, M.A.: Forbidden Substrings, Kolmogorov Complexity and Almost Periodic Sequences. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol. 3884, pp. 396–407. Springer, Heidelberg (2006)
Li, M., Vitanyi, P.: An Introduction to Kolmogorov Complexity and Its Applications, 2nd edn. Springer, NY (1997)
Motwani, R., Raghavan, P.: Randomized algorithms. Cambridge University Press, New York (1995)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Rumyantsev, A.Y. (2007). Kolmogorov Complexity, Lovász Local Lemma and Critical Exponents. In: Diekert, V., Volkov, M.V., Voronkov, A. (eds) Computer Science – Theory and Applications. CSR 2007. Lecture Notes in Computer Science, vol 4649. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-74510-5_35
Download citation
DOI: https://doi.org/10.1007/978-3-540-74510-5_35
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-74509-9
Online ISBN: 978-3-540-74510-5
eBook Packages: Computer ScienceComputer Science (R0)