Topological arguments for Kolmogorov complexity - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Proceedings/Recueil Des Communications Année : 2012

Topological arguments for Kolmogorov complexity

Andrei Romashchenko
Connectez-vous pour contacter l'auteur
Systèmes complexes, automates et pavages
CV
Alexander Shen
Systèmes complexes, automates et pavages

Résumé

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.

Domaines

Complexité [cs.CC]
Fichier principal
Vignette du fichier
topology-automata.pdf (113.15 Ko) Télécharger le fichier
Origine Fichiers éditeurs autorisés sur une archive ouverte

Andrei Romashchenko  : Connectez-vous pour contacter le contributeur

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

Soumis le : jeudi 27 septembre 2012-16:10:10

Dernière modification le : dimanche 17 novembre 2024-23:22:00

Archivage à long terme le : vendredi 16 décembre 2016-18:18:05

Télécharger pour visualiser

Dates et versions

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

Identifiants

  • HAL Id : lirmm-00736127 , version 1

Citer

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

Exporter

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

CNRS ESCAPE LIRMM MIPS UNIV-MONTPELLIER
133 Consultations
262 Téléchargements

Partager

More