Topological arguments for Kolmogorov complexity - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2012

Topological arguments for Kolmogorov complexity


We present several application of simple topological arguments in problems of Kolmogorov complexity. Basically we use the standard fact from topology that the disk is simply connected. It proves to be enough to construct strings with some nontrivial algorithmic properties.
Fichier principal
Vignette du fichier
topology-automata.pdf (113.15 Ko) Télécharger le fichier
Origin Publisher files allowed on an open archive

Dates and versions

lirmm-00736127 , version 1 (27-09-2012)


  • HAL Id : lirmm-00736127 , version 1


Andrei Romashchenko, Alexander Shen. Topological arguments for Kolmogorov complexity. AUTOMATA, Sep 2012, La Marana, Furiani, France. pp.127-132. ⟨lirmm-00736127⟩
118 View
241 Download


Gmail Mastodon Facebook X LinkedIn More