Coordination through de Bruijn sequences

Olivier Gossner; Penélope Hernández

doi:10.1016/j.orl.2005.01.006

Coordination through de Bruijn sequences

Olivier Gossner
, Penélope Hernández

Paris-Jourdan Sciences Economiques
Universidad de Alicante

Research output: Contribution to journal › Article › peer-review

3 Citations (Scopus)

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.

Original language	English
Pages (from-to)	17-21
Number of pages	5
Journal	Operations Research Letters
Volume	34
Issue number	1
DOIs	https://doi.org/10.1016/j.orl.2005.01.006
Publication status	Published - 1 Jan 2006
Externally published	Yes

Keywords

Automata
Complexity
Coordination
De Bruijn sequences

Access to Document

10.1016/j.orl.2005.01.006

Cite this

@article{cec1080b462d446d85f7764cda07993c,

title = "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.",

keywords = "Automata, Complexity, Coordination, De Bruijn sequences",

author = "Olivier Gossner and Pen{\'e}lope Hern{\'a}ndez",

year = "2006",

month = jan,

day = "1",

doi = "10.1016/j.orl.2005.01.006",

language = "English",

volume = "34",

pages = "17--21",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

T1 - Coordination through de Bruijn sequences

AU - Gossner, Olivier

AU - Hernández, Penélope

PY - 2006/1/1

Y1 - 2006/1/1

N2 - 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.

AB - 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.

KW - Automata

KW - Complexity

KW - Coordination

KW - De Bruijn sequences

U2 - 10.1016/j.orl.2005.01.006

DO - 10.1016/j.orl.2005.01.006

M3 - Article

AN - SCOPUS:28044459798

SN - 0167-6377

VL - 34

SP - 17

EP - 21

JO - Operations Research Letters

JF - Operations Research Letters

IS - 1

ER -

Coordination through de Bruijn sequences

Abstract

Keywords

Access to Document

Fingerprint

Cite this