Coordination through De Bruijn sequences

Abstract : Let (xt) be an n-periodic sequence in which the first n elements are drawn i.i.d. according to some rational distribution. We prove there exists a constant C such that whenever mlnm⩾Cn, with probability close to 1, there exists an automaton of size m that matches the sequence at almost all stages.
Type de document :
Article dans une revue
Operations Research Letters, Elsevier, 2006, 34 (1), pp.17-21. 〈10.1016/j.orl.2005.01.006〉
Liste complète des métadonnées

https://hal-pjse.archives-ouvertes.fr/halshs-00754177
Contributeur : Caroline Bauer <>
Soumis le : mardi 20 novembre 2012 - 08:47:08
Dernière modification le : vendredi 13 avril 2018 - 20:12:01

Identifiants

Collections

Citation

Olivier Gossner, Penelope Hernandez. Coordination through De Bruijn sequences. Operations Research Letters, Elsevier, 2006, 34 (1), pp.17-21. 〈10.1016/j.orl.2005.01.006〉. 〈halshs-00754177〉

Partager

Métriques

Consultations de la notice

223