Advertisement
Published in:
2019 | OriginalPaper | Chapter
Behavioral Strengths and Weaknesses of Various Models of Limited Automata
Author : Tomoyuki Yamakami
Published in: SOFSEM 2019: Theory and Practice of Computer Science
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
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 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 model is k-limited probabilistic automaton (k-lpa), which accepts an input exactly when its accepting states are reachable from its initial state with probability more than 1/2. We further study the behaviors of one-sided-error and bounded-error variants of such k-lpa’s as well as deterministic and nondeterministic models. We discuss fundamental properties of those machine models and obtain inclusions and separations among language families induced by these machine models. 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.