Fooling a two-way nondeterministic multihead automaton with reversal number restriction (Q1058864)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3902071
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Fooling a two-way nondeterministic multihead automaton with reversal number restriction |
scientific article; zbMATH DE number 3902071 |
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
0.87074864
0 references
0 references
0.8486414
0 references
0.8480123
0 references
0.84387046
0 references
0.84387046
0 references
0.84200597
0 references
