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

Economics

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

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 (US)
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
State	Published - Jan 2006

Keywords

Automata
Complexity
Coordination
De Bruijn sequences

ASJC Scopus subject areas

Software
Management Science and Operations Research
Industrial and Manufacturing Engineering
Applied Mathematics

Access to Document

10.1016/j.orl.2005.01.006

Cite this

@article{d8e5ba3691204e1480857237295f3857,

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,

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

language = "English (US)",

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

Y1 - 2006/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

UR - http://www.scopus.com/inward/record.url?scp=28044459798&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=28044459798&partnerID=8YFLogxK

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

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this