Fooling a two-way nondeterministic multihead automaton with reversal number restriction
type: Item
instance of: scholarly article
title: Fooling a two-way nondeterministic multihead automaton with reversal number restriction
zbMATH Open document ID: 0565.68078
published in: Acta Informatica
publication date: 1985-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 3902071
zbMATH Keywords: multihead finite automaton
zbMATH Keywords: two-way finite automata
zbMATH Keywords: nondeterminism
author: Juraj Hromkovič
MaRDI profile type: Publication
Recommended article: Two-Way Reversible Multi-Head Finite Automata
Recommended article: Q3793732
Recommended article: On two-way nondeterministic finite automata with one reversal-bounded counter
Recommended article: A Deterministic Two-Way Multi-head Finite Automaton Can Be Converted into a Reversible One with the Same Number of Heads
Recommended article: Simulating one-reversal multicounter machines by partially blind multihead finite automata
Recommended article: Q4941906
Recommended article: One-Way Reversible Multi-head Finite Automata
Recommended article: One-way reversible multi-head finite automata
Recommended article: One-reversal counter machines and multihead automata: revisited
Recommended article: One-Reversal Counter Machines and Multihead Automata: Revisited
description: scientific article; zbMATH DE number 3902071