HAL TEI export of lirmm-00736127 CCSD CC0 1.0 - Universal

HAL API Platform

 Topological arguments for Kolmogorov complexity Alexander Shen 329ba6bbfafe98e31b12df1f8d40f4dc gmail.com alexander-shen 12768 27802-12768 https://orcid.org/0000-0001-8605-7734 https://www.idref.fr/074188569 Andrei Romashchenko 98c085f266726e07926c57354c375025 ens-lyon.fr andrei-romashchenko 81 17831-81 http://www.researcherid.com/rid/H-7456-2012 https://orcid.org/0000-0001-7723-7880 https://www.idref.fr/165481277 http://www.researcherid.com/rid/http://www.researcherid.com/rid/H-7456-2012 https://arxiv.org/a/romashchenko_a_1 https://scholar.google.fr/citations?user=WmvoaNcAAAAJ Andrei Romashchenko c143839ff1ebb1a2528efa601d5185d0 lirmm.fr 2012-09-27 16:10:10 2026-02-12 03:25:37 2012-10-30 14:03:03 2012-09-19 2012-09-27 contributor Andrei Romashchenko c143839ff1ebb1a2528efa601d5185d0 lirmm.fr CCSD lirmm-00736127 https://hal-lirmm.ccsd.cnrs.fr/lirmm-00736127 shen:lirmm-00736127 <i>AUTOMATA</i>, Sep 2012, La Marana, Corsica, France. pp.127-132, <a target="_blank" href="https://dx.doi.org/10.4204/EPTCS.90.10">&#x27E8;10.4204/EPTCS.90.10&#x27E9;</a> AUTOMATA, Sep 2012, La Marana, Corsica, France. pp.127-132, &#x27E8;10.4204/EPTCS.90.10&#x27E9; HAL Authorization CNRS - Centre national de la recherche scientifique Université de Montpellier Paul-Valéry Université Perpignan Via Domitia Systèmes complexes, automates et pavages Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier Mathématiques, Informatique, Physique et Systèmes Université de Montpellier Publications UPVM texte intégral Université de Montpellier (2015-2021) Université de Montpellier - EPE International No No Yes Yes Topological arguments for Kolmogorov complexity Alexander Shen 329ba6bbfafe98e31b12df1f8d40f4dc gmail.com alexander-shen 12768 27802-12768 https://orcid.org/0000-0001-8605-7734 https://www.idref.fr/074188569 Andrei Romashchenko 98c085f266726e07926c57354c375025 ens-lyon.fr andrei-romashchenko 81 17831-81 http://www.researcherid.com/rid/H-7456-2012 https://orcid.org/0000-0001-7723-7880 https://www.idref.fr/165481277 http://www.researcherid.com/rid/http://www.researcherid.com/rid/H-7456-2012 https://arxiv.org/a/romashchenko_a_1 https://scholar.google.fr/citations?user=WmvoaNcAAAAJ AUTOMATA 2012-09-19 2012-09-21 La Marana, Corsica France 90 127-132 2012-09-19 10.4204/EPTCS.90.10 English Computer Science [cs]/Computational Complexity [cs.CC] Conference papers Conference papers Conference papers

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.

 Systèmes complexes, automates et pavages ESCAPE 2021-12-31
LIRMM, 161 rue Ada, 34000 Montpellier
https://www.lirmm.fr/equipes/ESCAPE/ 02636817X 0000000122597504 https://ror.org/02feahw73 Centre National de la Recherche Scientifique CNRS 1939-10-19
https://www.cnrs.fr/ 139590827 0000000405990488 199111950H https://ror.org/013yean28 Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier LIRMM 2022-01-01
161 rue Ada - 34095 Montpellier
https://www.lirmm.fr 139590827 0000000405990488 199111950H https://ror.org/013yean28 Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier LIRMM 1995-01-01 2021-12-31
161 rue Ada - 34095 Montpellier
https://www.lirmm.fr 0000000120970141 https://ror.org/051escj72 Université de Montpellier UM 2021-12-31
163 rue Auguste Broussonnet - 34090 Montpellier
http://www.umontpellier.fr/ https://ror.org/03am2jy38 Université de Perpignan Via Domitia UPVD
52 avenue Paul Alduy - 66860 Perpignan Cedex 9
http://www.univ-perp.fr/ https://ror.org/02kvxyf05 Institut National de Recherche en Informatique et en Automatique Inria
Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex
http://www.inria.fr/en/ https://ror.org/051escj72 Université de Montpellier UM 2022-01-01
163 rue Auguste Broussonnet - 34090 Montpellier
http://www.umontpellier.fr/ 282217916 Université de Montpellier Paul-Valéry UMPV 2025-01-01
Université de Montpellier Paul-Valéry Route de Mende 34199 Montpellier Cedex 5
https://www.univ-montp3.fr/fr