Skip to Main content Skip to Navigation
Conference papers

Topological arguments for Kolmogorov complexity

Andrei Romashchenko 1, * Alexander Shen 1
* Corresponding author
1 ESCAPE - Systèmes complexes, automates et pavages
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [3 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00736127
Contributor : Andrei Romashchenko <>
Submitted on : Thursday, September 27, 2012 - 4:10:10 PM
Last modification on : Wednesday, May 13, 2020 - 3:02:09 PM
Document(s) archivé(s) le : Friday, December 16, 2016 - 6:18:05 PM

File

topology-automata.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : lirmm-00736127, version 1

Collections

Citation

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

Share

Metrics

Record views

246

Files downloads

370