Coordination through De Bruijn sequences - Archive ouverte HAL Access content directly
Journal Articles Operations Research Letters Year : 2006

Coordination through De Bruijn sequences

(1) , (2)
1
2

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.

Dates and versions

halshs-00754177 , version 1 (20-11-2012)

Identifiers

Cite

Olivier Gossner, Penelope Hernandez. Coordination through De Bruijn sequences. Operations Research Letters, 2006, 34 (1), pp.17-21. ⟨10.1016/j.orl.2005.01.006⟩. ⟨halshs-00754177⟩
136 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More