Topological arguments for Kolmogorov complexity - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Proceedings Year : 2012

Topological arguments for Kolmogorov complexity

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.

Domains

Computational Complexity [cs.CC]
Fichier principal
Vignette du fichier
topology-automata.pdf (113.15 Ko) Télécharger le fichier
Origin Publisher files allowed on an open archive

Andrei Romashchenko  : Connect in order to contact the contributor

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00736127

Submitted on : Thursday, September 27, 2012-4:10:10 PM

Last modification on : Sunday, November 17, 2024-11:22:00 PM

Long-term archiving on : Friday, December 16, 2016-6:18:05 PM

Download

Dates and versions

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

Identifiers

  • HAL Id : lirmm-00736127 , version 1

Cite

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

Export

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

CNRS ESCAPE LIRMM MIPS UNIV-MONTPELLIER
133 View
272 Download

Share

More