On Computational Power of Partially Blind Automata
Pavol Ďuriš · Journal of Applied Mathematics Statistics and Informatics · 2012
On Computational Power of Partially Blind Automata In this paper we deal with 1-way multihead finite automata, in which the symbol under only one head (called read head) controls its move and other heads cannot distinguish the input symbols, they can only distinguish the end-marker from the other input symbols and they are called the blind head. We call such automaton a partially blind multihead automaton. We prove that partially blind k + 1-head finite automata are more powerful than such k-head finite automata. We show also that nondeterministic partially blind k-head finite automata languages are not closed under iteration and intersection for any k ≥ 2, and moreover, deterministic partially blind k head finite automata languages are not closed under intersection, union, complementation and reversal for any k ≥ 2. Finally we prove that deterministic partially blind k-head finite automata with endmarker are more powerful that such automata without endmarker for each k ≥ 4.