COORDINATION THROUGH DE BRUIJN SEQUENCES
Olivier Gossner and
Penelope Hernandez (penelope.hernandez@uv.es)
Working Papers. Serie AD from Instituto Valenciano de Investigaciones Económicas, S.A. (Ivie)
Abstract:
Let µ be a rational distribution over a finite alphabet, and ( ) be a n-periodic sequences which first n elements are drawn i.i.d. according to µ. We consider automata of bounded size that input and output at stage t. We prove the existence of a constant C such that, whenever , with probability close to 1 there exists an automaton of size m such that the empirical frequency of stages such that is close to 1. In particular, one can take , where and .
Keywords: Coordination; complexity; De Bruijn sequences; automata (search for similar items in EconPapers)
Pages: 12 pages
Date: 2005-02
New Economics Papers: this item is included in nep-mic
References: Add references at CitEc
Citations: View citations in EconPapers (2)
Published by Ivie
Downloads: (external link)
http://www.ivie.es/downloads/docs/wpasad/wpasad-2005-05.pdf Fisrt version / Primera version, 2005 (application/pdf)
Related works:
Working Paper: Coordination through De Bruijn sequences (2006)
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:ivi:wpasad:2005-05
Access Statistics for this paper
More papers in Working Papers. Serie AD from Instituto Valenciano de Investigaciones Económicas, S.A. (Ivie) Contact information at EDIRC.
Bibliographic data for series maintained by Departamento de Edición (edicion@ivie.es).