COORDINATION THROUGH DE BRUIJN SEQUENCES

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 .

MoreLess

Year of publication:	2005-02
Authors:	Gossner, Olivier ; Hernández, Penélope
Institutions:	Instituto Valenciano de Investigaciones Económicas (IVIE)
Subject:	Coordination \| complexity \| De Bruijn sequences \| automata

More details

Extent:	application/pdf
Series:	Working Papers. Serie AD.
Type of publication:	Book / Working Paper
Language:	English
Notes:	Published by Ivie 12 pages
Source:	RePEc - Research Papers in Economics

Persistent link: https://www.econbiz.de/10005731250