Fooling a two-way nondeterministic multihead automaton with reversal number restriction (Q1058864)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Fooling a two-way nondeterministic multihead automaton with reversal number restriction |
scientific article |
Statements
Fooling a two-way nondeterministic multihead automaton with reversal number restriction (English)
0 references
1985
0 references
We define a language L and show that it can be recognized by no two-way nondeterministic sensing multihead finite automaton with \(n^ a\) reversal bound, where n is the length of input words, and \(1/3>a>0\) is a real number. Since L is recognized by a two-way deterministic two-head finite automaton working in linear time we obtain, for two-way finite automata, that time, reading heads, and nondeterminism as resources cannot compensate for the reversal number restriction.
0 references
multihead finite automaton
0 references
two-way finite automata
0 references
nondeterminism
0 references