<?xml version="1.0" encoding="utf-8"?>
<TEI xmlns="http://www.tei-c.org/ns/1.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:hal="http://hal.archives-ouvertes.fr/" xmlns:gml="http://www.opengis.net/gml/3.3/" xmlns:gmlce="http://www.opengis.net/gml/3.3/ce" version="1.1" xsi:schemaLocation="http://www.tei-c.org/ns/1.0 http://api.archives-ouvertes.fr/documents/aofr-sword.xsd">
  <teiHeader>
    <fileDesc>
      <titleStmt>
        <title>HAL TEI export of lirmm-03059690</title>
      </titleStmt>
      <publicationStmt>
        <distributor>CCSD</distributor>
        <availability status="restricted">
          <licence target="https://creativecommons.org/publicdomain/zero/1.0/">CC0 1.0 - Universal</licence>
        </availability>
        <date when="2026-05-22T15:12:09+02:00"/>
      </publicationStmt>
      <sourceDesc>
        <p part="N">HAL API Platform</p>
      </sourceDesc>
    </fileDesc>
  </teiHeader>
  <text>
    <body>
      <listBibl>
        <biblFull>
          <titleStmt>
            <title xml:lang="en">Automatic Kolmogorov complexity, normality, and finite state dimension revisited (extended version 6, 2020)</title>
            <author role="aut">
              <persName>
                <forename type="first">Alexander</forename>
                <surname>Kozachinskiy</surname>
              </persName>
              <idno type="halauthorid">1690838-0</idno>
              <affiliation ref="#struct-466917"/>
            </author>
            <author role="aut">
              <persName>
                <forename type="first">Alexander</forename>
                <surname>Shen</surname>
              </persName>
              <email type="md5">329ba6bbfafe98e31b12df1f8d40f4dc</email>
              <email type="domain">gmail.com</email>
              <idno type="idhal" notation="string">alexander-shen</idno>
              <idno type="idhal" notation="numeric">12768</idno>
              <idno type="halauthorid" notation="string">27802-12768</idno>
              <idno type="ORCID">https://orcid.org/0000-0001-8605-7734</idno>
              <idno type="IDREF">https://www.idref.fr/074188569</idno>
              <orgName ref="#struct-181"/>
              <affiliation ref="#struct-394760"/>
            </author>
            <editor role="depositor">
              <persName>
                <forename>Alexander</forename>
                <surname>Shen</surname>
              </persName>
              <email type="md5">2b8926984c81332f1951931bfd2fefc6</email>
              <email type="domain">lirmm.fr</email>
            </editor>
            <funder ref="#projanr-42137"/>
          </titleStmt>
          <editionStmt>
            <edition n="v1" type="current">
              <date type="whenSubmitted">2020-12-12 23:51:59</date>
              <date type="whenWritten">2020-08-25</date>
              <date type="whenModified">2025-11-21 08:43:54</date>
              <date type="whenReleased">2020-12-15 15:46:22</date>
              <date type="whenProduced">2020-08-25</date>
              <date type="whenEndEmbargoed">2020-12-12</date>
              <ref type="file" target="https://hal-lirmm.ccsd.cnrs.fr/lirmm-03059690v1/document">
                <date notBefore="2020-12-12"/>
              </ref>
              <ref type="file" subtype="author" n="1" target="https://hal-lirmm.ccsd.cnrs.fr/lirmm-03059690v1/file/1701.09060.pdf" id="file-3059690-2688670">
                <date notBefore="2020-12-12"/>
              </ref>
            </edition>
            <respStmt>
              <resp>contributor</resp>
              <name key="417184">
                <persName>
                  <forename>Alexander</forename>
                  <surname>Shen</surname>
                </persName>
                <email type="md5">2b8926984c81332f1951931bfd2fefc6</email>
                <email type="domain">lirmm.fr</email>
              </name>
            </respStmt>
          </editionStmt>
          <publicationStmt>
            <distributor>CCSD</distributor>
            <idno type="halId">lirmm-03059690</idno>
            <idno type="halUri">https://hal-lirmm.ccsd.cnrs.fr/lirmm-03059690</idno>
            <idno type="halBibtex">kozachinskiy:lirmm-03059690</idno>
            <idno type="halRefHtml">2020</idno>
            <idno type="halRef">2020</idno>
            <availability status="restricted">
              <licence target="https://creativecommons.org/licenses/by/4.0/">CC BY 4.0 - Attribution<ref corresp="#file-3059690-2688670"/></licence>
            </availability>
          </publicationStmt>
          <seriesStmt>
            <idno type="stamp" n="CNRS">CNRS - Centre national de la recherche scientifique</idno>
            <idno type="stamp" n="ESCAPE" corresp="LIRMM">Systèmes complexes, automates et pavages</idno>
            <idno type="stamp" n="LIRMM">Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier</idno>
            <idno type="stamp" n="MIPS">Mathématiques, Informatique, Physique et Systèmes</idno>
            <idno type="stamp" n="UNIV-MONTPELLIER">Université de Montpellier</idno>
            <idno type="stamp" n="ANR">ANR</idno>
            <idno type="stamp" n="UM-2015-2021" corresp="UNIV-MONTPELLIER">Université de Montpellier (2015-2021)</idno>
            <idno type="stamp" n="TEST3-HALCNRS">TEST3-HALCNRS</idno>
            <idno type="stamp" n="ANR_QUANTIQUE">ANR QUANTIQUE</idno>
            <idno type="stamp" n="ANR_QUANTIQUE_2" corresp="ANR_QUANTIQUE">ANR_QUANTIQUE_2</idno>
          </seriesStmt>
          <notesStmt>
            <note type="commentary">This is an exteneded version: a section that includes a characterization of finite-state dimension in terms of finite-state apriori probability and block frequencies is added.</note>
          </notesStmt>
          <sourceDesc>
            <biblStruct>
              <analytic>
                <title xml:lang="en">Automatic Kolmogorov complexity, normality, and finite state dimension revisited (extended version 6, 2020)</title>
                <author role="aut">
                  <persName>
                    <forename type="first">Alexander</forename>
                    <surname>Kozachinskiy</surname>
                  </persName>
                  <idno type="halauthorid">1690838-0</idno>
                  <affiliation ref="#struct-466917"/>
                </author>
                <author role="aut">
                  <persName>
                    <forename type="first">Alexander</forename>
                    <surname>Shen</surname>
                  </persName>
                  <email type="md5">329ba6bbfafe98e31b12df1f8d40f4dc</email>
                  <email type="domain">gmail.com</email>
                  <idno type="idhal" notation="string">alexander-shen</idno>
                  <idno type="idhal" notation="numeric">12768</idno>
                  <idno type="halauthorid" notation="string">27802-12768</idno>
                  <idno type="ORCID">https://orcid.org/0000-0001-8605-7734</idno>
                  <idno type="IDREF">https://www.idref.fr/074188569</idno>
                  <orgName ref="#struct-181"/>
                  <affiliation ref="#struct-394760"/>
                </author>
              </analytic>
              <monogr>
                <imprint/>
              </monogr>
            </biblStruct>
          </sourceDesc>
          <profileDesc>
            <langUsage>
              <language ident="en">English</language>
            </langUsage>
            <textClass>
              <keywords scheme="author">
                <term xml:lang="en">normal sequences</term>
                <term xml:lang="en">finite-state dimension</term>
                <term xml:lang="en">finite-state complexity</term>
                <term xml:lang="en">finite-state gales</term>
              </keywords>
              <classCode scheme="halDomain" n="info.info-it">Computer Science [cs]/Information Theory [cs.IT]</classCode>
              <classCode scheme="halDomain" n="math.math-lo">Mathematics [math]/Logic [math.LO]</classCode>
              <classCode scheme="halDomain" n="math.math-pr">Mathematics [math]/Probability [math.PR]</classCode>
              <classCode scheme="halTypology" n="UNDEFINED">Preprints, Working Papers, ...</classCode>
              <classCode scheme="halOldTypology" n="UNDEFINED">Preprints, Working Papers, ...</classCode>
              <classCode scheme="halTreeTypology" n="UNDEFINED">Preprints, Working Papers, ...</classCode>
            </textClass>
            <abstract xml:lang="en">
              <p>It is well known that normality (all factors of a given length appear in an infinite sequence with the same frequency) can be described as incompressibility via finite automata. Still the statement and the proof of this result as given by Becher and Heiber [9] in terms of "lossless finite-state compressors" do not follow the standard scheme of Kolmogorov complexity definition (an automaton is used for compression, not decompression). We modify this approach to make it more similar to the traditional Kolmogorov complexity theory (and simpler) by explicitly defining the notion of automatic Kolmogorov complexity and using its simple properties. Other known notions (Shallit-Wang [50], Calude-Salomaa-Roblot [16]) of description complexity related to finite automata are discussed (see the last section). Using this characterization, we provide easy proofs for most of the classical results about normal sequences, including the equivalence between aligned and non-aligned definitions of normality, the Piatetski-Shapiro sufficient condition for normality (in a strong form), and Wall's theorem saying that a normal real number remains normal when multiplied by a rational number or when a rational number is added. Using the same characterization, we prove a sufficient condition for normality of a sequence in terms of Kolmogorov complexity. This condition implies the normality of Champernowne's sequence as well as some generalizations of this result (provided by Champernowne himself, Besicovitch, Copeland and Erdös). It can be also used to give a simple proof of the result of Calude-Staiger-Stephan [17] saying that normality cannot be characterized in terms of the automatic complexity notion introduced by Calude-Salomaa-Roblot [16]. Then we extend this approach to finite state dimension showing that automatic Kolmogorov complexity can be used to characterize the finite state dimension (defined by Dai, Lathrop, Lutz and Mayordomo in [23]). We start with the block entropy definition of the finite state dimension given by Bourke, Hitchcock and Vinogradchandran [14] and show that one may use non-aligned blocks in this definition.</p>
            </abstract>
          </profileDesc>
        </biblFull>
      </listBibl>
    </body>
    <back>
      <listOrg type="structures">
        <org type="institution" xml:id="struct-466917" status="VALID">
          <idno type="IdRef">254429351</idno>
          <orgName>Vysšaja škola èkonomiki = National Research University Higher School of Economics [Moscow]</orgName>
          <orgName type="acronym">HSE</orgName>
          <date type="start">1992-01-01</date>
          <desc>
            <address>
              <addrLine>20 Myasnitskaya Ulitsa, 101000 Moscow</addrLine>
              <country key="RU"/>
            </address>
            <ref type="url">https://www.hse.ru/en/</ref>
          </desc>
        </org>
        <org type="researchteam" xml:id="struct-394760" status="OLD">
          <orgName>Systèmes complexes, automates et pavages</orgName>
          <orgName type="acronym">ESCAPE</orgName>
          <date type="end">2021-12-31</date>
          <desc>
            <address>
              <addrLine>LIRMM, 161 rue Ada, 34000 Montpellier</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">https://www.lirmm.fr/equipes/ESCAPE/</ref>
          </desc>
          <listRelation>
            <relation active="#struct-181" type="direct"/>
            <relation name="UMR5506" active="#struct-410122" type="indirect"/>
            <relation name="UMR5506" active="#struct-441569" type="indirect"/>
          </listRelation>
        </org>
        <org type="laboratory" xml:id="struct-181" status="OLD">
          <idno type="IdRef">139590827</idno>
          <idno type="ISNI">0000000405990488</idno>
          <idno type="RNSR">199111950H</idno>
          <idno type="ROR">https://ror.org/013yean28</idno>
          <orgName>Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier</orgName>
          <orgName type="acronym">LIRMM</orgName>
          <date type="start">1995-01-01</date>
          <date type="end">2021-12-31</date>
          <desc>
            <address>
              <addrLine>161 rue Ada - 34095 Montpellier</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">https://www.lirmm.fr</ref>
          </desc>
          <listRelation>
            <relation name="UMR5506" active="#struct-410122" type="direct"/>
            <relation name="UMR5506" active="#struct-441569" type="direct"/>
          </listRelation>
        </org>
        <org type="institution" xml:id="struct-410122" status="OLD">
          <idno type="ISNI">0000000120970141</idno>
          <idno type="ROR">https://ror.org/051escj72</idno>
          <orgName>Université de Montpellier</orgName>
          <orgName type="acronym">UM</orgName>
          <date type="end">2021-12-31</date>
          <desc>
            <address>
              <addrLine>163 rue Auguste Broussonnet - 34090 Montpellier</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">http://www.umontpellier.fr/</ref>
          </desc>
        </org>
        <org type="regroupinstitution" xml:id="struct-441569" status="VALID">
          <idno type="IdRef">02636817X</idno>
          <idno type="ISNI">0000000122597504</idno>
          <idno type="ROR">https://ror.org/02feahw73</idno>
          <orgName>Centre National de la Recherche Scientifique</orgName>
          <orgName type="acronym">CNRS</orgName>
          <date type="start">1939-10-19</date>
          <desc>
            <address>
              <country key="FR"/>
            </address>
            <ref type="url">https://www.cnrs.fr/</ref>
          </desc>
        </org>
      </listOrg>
      <listOrg type="projects">
        <org type="anrProject" xml:id="projanr-42137" status="VALID">
          <idno type="anr">ANR-15-CE40-0016</idno>
          <idno type="program">Fondements du numérique</idno>
          <orgName>RaCAF</orgName>
          <desc>Dépasser les frontières de l'aléatoire et du calculable</desc>
          <date type="start">2015</date>
        </org>
      </listOrg>
    </back>
  </text>
</TEI>