Article ID Journal Published Year Pages File Type
1143451 Operations Research Letters 2006 5 Pages PDF
Abstract

Let (xt)(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⩾Cnmlnm⩾Cn, with probability close to 1, there exists an automaton of size m that matches the sequence at almost all stages.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,