Coordination through De Bruijn sequences |
| |
| Authors: | Olivier Gossner,Pené lope Herná ndez |
| |
| Affiliation: | a Paris-Jourdan Sciences Économiques, UMR CNRS - EHESS - ENPC - ENS 8545, 48 boulevard Jourdan, 75014 Paris, France
b Departmento Fundamentos del Análisis Económico, Universidad de Alicante, Carretera de San Vicente s/n, 03080 San Vicente, Alicante, Spain |
| |
| 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 |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
