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
    0 references

    Identifiers