<abstract xml:lang="en" xmlns="http://www.w3.org/1999/xhtml"><p>In this paper we deal with 1-way multihead finite automata, in which the symbol under only one head (called <italic>read</italic> 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 <italic>blind</italic> head. We call such automaton a partially blind multihead automaton. We prove that partially blind <italic>k</italic> + 1-head finite automata are more powerful than such <italic>k</italic>-head finite automata. We show also that nondeterministic partially blind <italic>k</italic>-head finite automata languages are not closed under iteration and intersection for any <italic>k</italic> ≥ 2, and moreover, deterministic partially blind <italic>k</italic> head finite automata languages are not closed under intersection, union, complementation and reversal for any <italic>k</italic> ≥ 2. Finally we prove that deterministic partially blind <italic>k</italic>-head finite automata with endmarker are more powerful that such automata without endmarker for each <italic>k</italic> ≥ 4.</p></abstract>

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.

On Computational Power of Partially Blind Automata

Department of Informatics Faculty of Mathematics, Physics and Informatics Comenius University, Bratislava

Journal of Applied Mathematics, Statistics and Informatics

{"article-title":"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...

On Computational Power of Partially Blind Automata

Data publikacji: 13 sie 2012

Zakres stron: 33 - 41

DOI: https://doi.org/10.2478/v10294-012-0003-5

Słowa kluczowe
one-way finite automata, multihead finite automata, blind head

This content is open access.

On Computational Power of Partially Blind Automata

Data publikacji: 13 sie 2012

Zakres stron: 33 - 41

DOI: https://doi.org/10.2478/v10294-012-0003-5

Słowa kluczoweone-way finite automata, multihead finite automata, blind head

This content is open access.

Słowa kluczowe
one-way finite automata, multihead finite automata, blind head