Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR11-107 | 22nd July 2011 16:05

On Computational Power of Partially Blind Automata


Authors: Pavol Duris
Publication: 8th August 2011 16:36
Downloads: 1050


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\ge 2$, and moreover, deterministic partially blind $k$ head finite automata languages are not closed under intersection, union, complementation and reversal for any $k\ge 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\ge 4$.

ISSN 1433-8092 | Imprint