Topological arguments for Kolmogorov complexity - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Communication Dans Un Congrès 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 : vendredi 24 mars 2023-14:52:56

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, Sep 2012, La Marana, Furiani, France. pp.127-132. ⟨lirmm-00736127⟩

Exporter

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

CNRS ESCAPE LIRMM MIPS UNIV-MONTPELLIER
118 Consultations
240 Téléchargements

Partager

Gmail Facebook X LinkedIn More