Learning Cycle Length through Finite Automata
AbstractWe 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 terminal state. We analyze the worst 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 cannot be solved in deterministic SPACE X TIME smaller than (n^2). 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 positive L
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoPaper provided by The Center for the Study of Rationality, Hebrew University, Jerusalem in its series Discussion Paper Series with number dp546.
Length: 8 pages
Date of creation: Apr 2010
Date of revision:
This paper has been announced in the following NEP Reports:
- NEP-ALL-2010-06-11 (All new papers)
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Abraham Neyman, 2008.
"Learning Effectiveness and Memory Size,"
Discussion Paper Series
dp476, The Center for the Study of Rationality, Hebrew University, Jerusalem.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Ilan Nehama).
If references are entirely missing, you can add them using this form.