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
Departmento Fundamentos del Análisis Económico
Universidad de Alicante

Résultats de recherche: Contribution à un journal › Article › Revue par des pairs

3 Citations (Scopus)

Résumé

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.

langue originale	Anglais
Pages (de - à)	17-21
Nombre de pages	5
journal	Operations Research Letters
Volume	34
Numéro de publication	1
Les DOIs	https://doi.org/10.1016/j.orl.2005.01.006
état	Publié - 1 janv. 2006
Modification externe	Oui

Accès au document

10.1016/j.orl.2005.01.006

Contient cette citation

@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

Résumé

Accès au document

Empreinte digitale

Contient cette citation