Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadata
Contributor : Caroline Bauer Connect in order to contact the contributor
Submitted on : Tuesday, November 20, 2012 - 8:47:08 AM
Last modification on : Wednesday, November 17, 2021 - 12:29:12 PM

Links full text




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⟩



Les métriques sont temporairement indisponibles