Coordination through De Bruijn sequences

Olivier Gossner and Penelope Hernandez ()

Post-Print from HAL

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.

Keywords: Coordination; Complexity; De Bruijn sequences; Automata (search for similar items in EconPapers)
Date: 2006-01
References: Add references at CitEc
Citations: View citations in EconPapers (4)

Published in Operations Research Letters, 2006, 34 (1), pp.17-21. ⟨10.1016/j.orl.2005.01.006⟩

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
Working Paper: COORDINATION THROUGH DE BRUIJN SEQUENCES (2005)
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hal:journl:halshs-00754177

DOI: 10.1016/j.orl.2005.01.006

Access Statistics for this paper

More papers in Post-Print from HAL
Bibliographic data for series maintained by CCSD ().