Multi angle

H 1 Independence of normal words

Auteurs : Becher, Verónica (Auteur de la Conférence)
CIRM (Editeur )

    Loading the player...

    Résumé : Recall that normality is a elementary form of randomness: an infinite word is normal to a given alphabet if all blocks of symbols of the same length occur in the word with the same asymptotic frequency. We consider a notion of independence on pairs of infinite words formalising that two words are independent if no one helps to compress the other using one-to-one finite transducers with two inputs. As expected, the set of independent pairs has Lebesgue measure 1. We prove that not only the join of two normal words is normal, but, more generally, the shuffling with a finite transducer of two normal independent words is also a normal word. The converse of this theorem fails: we construct a normal word as the join of two normal words that are not independent. We construct a word x such that the symbol at position n is equal to the symbol at position 2n. Thus, x is the join of x itself and the subsequence of odd positions of x. We also show that selection by finite automata acting on pairs of independent words preserves normality. This is a counterpart version of Agafonov's theorem for finite automata with two input tapes.
    This is joint work with Olivier Carton (Universitéé Paris Diderot) and Pablo Ariel Heiber (Universidad de Buenos Aires).

    Keywords : normal numbers; finite state automata; combinatorics on words

    Codes MSC :
    11K16 - Normal numbers, radix expansions, Pisot numbers, Salem numbers, good lattice points, etc.
    68R15 - Combinatorics on words
    03D32 - Algorithmic randomness and dimension

      Informations sur la Vidéo

      Langue : Anglais
      Date de publication : 06/07/2016
      Date de captation : 21/06/2016
      Collection : Research talks ; Computer Science ; Logic and Foundations
      Format : MP4
      Durée : 00:58:31
      Domaine : Computer Science ; Logic and Foundations
      Audience : Chercheurs ; Doctorants , Post - Doctorants
      Download : https://videos.cirm-math.fr/2016-06-21_Becher.mp4

    Informations sur la rencontre

    Nom de la rencontre : Computability, randomness and applications / Calculabilité, hasard et leurs applications
    Organisateurs de la rencontre : Bienvenu, Laurent ; Jeandel, Emmanuel ; Porter, Christopher
    Dates : 20/06/2016 - 24/06/2016
    Année de la rencontre : 2016
    URL Congrès : http://conferences.cirm-math.fr/1408.html

    Citation Data

    DOI : 10.24350/CIRM.V.19004903
    Cite this video as: Becher, Verónica (2016). Independence of normal words. CIRM. Audiovisual resource. doi:10.24350/CIRM.V.19004903
    URI : http://dx.doi.org/10.24350/CIRM.V.19004903

    Voir aussi


    1. Agafonov, V.N. (1968). Normal sequences and finite automata. Soviet Mathematics Doklady, 9, 324-325 - https://www.zbmath.org/?q=an:0242.94040

    2. Becher, V., Carton, O., & Heiber, P.A. (2015). Normality and automata. Journal of Computer and System Sciences, 81(8), 1592-1613 - http://dx.doi.org/10.1016/j.jcss.2015.04.007

    3. Becher, V., & Heiber, P.A. (2013). Normal numbers and finite automata. Theoretical Computer Science, 477, 109-116 - http://dx.doi.org/10.1016/j.tcs.2013.01.019

    4. Bugeaud, Y. (2012). Distribution modulo one and Diophantine approximation. Cambridge: Cambridge University Press - http://www.cambridge.org/us/academic/subjects/mathematics/number-theory/distribution-modulo-one-and-diophantine-approximation

    5. Carton, O., & Heiber, P.A. (2015). Normality and two-way automata. Information and Computation, 241, 264–276 - http://dx.doi.org/10.1016/j.ic.2015.02.001

    6. Schnorr, C.P., & Stimm, H. (1972). Endliche Automaten und Zufallsfolgen. Acta Informatica, 1, 345-359 - http://dx.doi.org/10.1007/BF00289514

Titres de périodiques et e-books électroniques (Depuis le CIRM)

Ressources Electroniques

Books & Print journals

Recherche avancée