## March 7: Learning Cycle Length with Finite Automata / Ron Peretz, HUJI

March 3, 2010 by ilannehama

Title: Learning Cycle Length with Finite Automata

Abstract:

We study the space and time automaton-complexity of the CYCLE-LENGTH problem. The input is a periodic stream of bits whose cycle length is bounded by a known number n. The output, a number between 1 and n, is the exact cycle length. We also study a related problem, CYCLE-DIVISOR. In the latter problem the output is a large number that divides the cycle length. That is, a number k >> 1 that divides the cycle length, or (in case the cycle length is small) the cycle length itself. The complexity is measured in terms of the SPACE, the logarithm of the number of states in an automaton that solves the problem, and the TIME required to reach a terminating state. We analyze the worse input against a deterministic (pure) automaton, and against a probabilistic (mixed) automaton. In the probabilistic case we require that the probability of computing a correct output is arbitrarily close to one. We establish the following results:

o CYCLE-DIVISOR can be solved in deterministic SPACE o(n), and TIME O(n).

o CYCLE-LENGTH can be solved in probabilistic SPACE o(n), and TIME O(n).

o CYCLE-LENGTH can be solved in deterministic SPACE O(nL), and TIME $O(n/L)$, for any small L > 0.

o CYCLE-LENGTH cannot be solved in deterministic (SPACE X TIME) smaller than $\Omega(n^2)$.

### Like this:

Like Loading...

*Related*

## Leave a Reply