Prediction with Restricted Resources and Finite Automata TeX Export

@article{citeulike:3773575, abstract = {We obtain an index of the complexity of a random sequence by allowing the role of the measure in classical probability theory to be played by a function we call the generating mechanism. Typically, this generating mechanism will be a finite automata. We generate a set of biased sequences by applying a finite state automata with a specified number, \$m\$, of states to the set of all binary sequences. Thus we can index the complexity of our random sequence by the number of states of the automata. We detail optimal algorithms to predict sequences generated in this way.}, archivePrefix = {arXiv}, author = {Macleod, Finn and Gleeson, James}, citeulike-article-id = {3773575}, citeulike-linkout-0 = {http://arxiv.org/abs/0812.1949}, citeulike-linkout-1 = {http://arxiv.org/pdf/0812.1949}, day = {10}, eprint = {0812.1949}, keywords = {automata, graph, prediction, theory}, month = {Dec}, posted-at = {2009-03-16 07:17:40}, priority = {1}, title = {Prediction with Restricted Resources and Finite Automata}, url = {http://arxiv.org/abs/0812.1949}, year = {2008} }

TY - JOUR ID - citeulike:3773575 L3 - citeulike-article-id:3773575 N2 - We obtain an index of the complexity of a random sequence by allowing the role of the measure in classical probability theory to be played by a function we call the generating mechanism. Typically, this generating mechanism will be a finite automata. We generate a set of biased sequences by applying a finite state automata with a specified number, $m$, of states to the set of all binary sequences. Thus we can index the complexity of our random sequence by the number of states of the automata. We detail optimal algorithms to predict sequences generated in this way. TI - Prediction with Restricted Resources and Finite Automata KW - automata KW - graph KW - prediction KW - theory AU - Macleod, Finn AU - Gleeson, James PY - 2008/Dec/10/ UR - http://arxiv.org/abs/0812.1949 ER -