Behavioral Strengths and Weaknesses of Various Models of Limited Automata
share
We examine the behaviors of various models of k-limited automata, which naturally extend Hibbard's [Inf. Control, vol. 11, pp. 196–238, 1967] scan limited automata, each of which is a single-tape linear-bounded automaton satisfying the k-limitedness requirement that the content of each tape cell should be modified only during the first k visits of a tape head. One central computation model is a probabilistic k-limited automaton (abbreviated as a k-lpa), which accepts an input exactly when its accepting states are reachable from its initial state with probability more than 1/2 within expected polynomial time. We also study the behaviors of one-sided-error and bounded-error variants of such k-lpa's as well as the deterministic, nondeterministic, and unambiguous models of k-limited automata, which can be viewed as natural restrictions of k-lpa's. We discuss fundamental properties of these machine models and obtain inclusions and separations among language families induced by them. In due course, we study special features – the blank skipping property and the closure under reversal – which are keys to the robustness of k-lpa's.
READ FULL TEXT