4 papers
Maximal Kolmogorov Complexity in a Hamming Ball
Alexander Kozachinskiy, Nikolay Vereshchagin
The minimal Kolmogorov complexity of a string within Hamming distance r of a given string x is the algorithmic rate-distortion function of x, and Vereshchagin and Vitanyi character…
Matching Rules for Substitution and Hierarchical Tilings for any Substitution with Finite Local Complexity
Nikolay Vereshchagin
The Goodman-Strauss theorem states that for ``almost every'' substitution , the family of substitution tilings is sofic, that is, it can be defined by local matching rules for s…
Goodman-Strauss theorem revisited
Nikolay Vereshchagin
The Goodman-Strauss theorem states that for ``almost every" substitution, the family of substitution tilings is sofic, that is, it can be defined by local rules for some decoration…
Descriptive Complexity of Computable Sequences Revisited
Nikolay Vereshchagin
The purpose of this paper is to answer two questions left open in [B. Durand, A. Shen, and N. Vereshchagin, Descriptive Complexity of Computable Sequences, Theoretical Computer Sci…