Alternating multihead finite automata
type: Item
instance of: scholarly article
title: Alternating multihead finite automata
zbMATH Open document ID: 0665.68064
DOI: 10.1016/0304-3975(88)90122-3
author: K. N. King
published in: Theoretical Computer Science
publication date: 1988-01-01T00:00:00Z
review text: [See also the review of the preliminary version of this paper, Lect. Notes Comput. Sci. 115, 506-520 (1981; Zbl 0471.68060).] We define alternating multihead finite automata, a generalization of nondeterministic multihead finite automata based on the alternating Turing machine model introduced by \textit{A. K. Chandra}, \textit{D. C. Kozen} and \textit{L. J. Stockmeyer} J. Assoc. Comput. Mach. 28, 114-133 (1981; Zbl 0473.68043). We study the relationships between the classes of languages accepted by alternating multihead finite automata and the classes accepted by deterministic and nondeterministic multihead finite automata and pushdown automata. We also examine basic questions about alternating multihead finite automata (for example, are \(k+1\) heads better than k ?). We conclude by placing upper bounds on the deterministic time and space complexity of the classes of languages accepted by alternating multihead finite automata. As corollaries to our results about alternating multihead finite automata, we obtain several facts about multihead pushdown automata, indicating that the study of alternating multihead finite automata may lead to useful results about nonalternating automata.
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 03D05
Mathematics Subject Classification ID: 68Q05
zbMATH DE Number: 4088958
zbMATH Keywords: alternating Turing machine
zbMATH Keywords: nondeterministic multihead finite automata
zbMATH Keywords: deterministic time and space complexity
zbMATH Keywords: multihead pushdown automata
zbMATH Keywords: alternating multihead finite automata
MaRDI profile type: Publication
full work available at URL: 0304-3975(88)90122-3
OpenAlex ID: W2061631274
cites work: Time and tape complexity of pushdown automaton languages
cites work: Alternation
cites work: Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
cites work: Q5670175
cites work: An observation on time-storage trade off
cites work: Propositional dynamic logic of regular programs
cites work: Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages
cites work: Q4198075
cites work: Multi-tape and multi-head pushdown automata
cites work: On non-determinacy in simple computing devices
cites work: On two-way multihead automata
cites work: Space-bounded reducibility among combinatorial problems
cites work: Complete problems for deterministic polynomial time
cites work: Pushdown automata with counters
cites work: Classes of Pebble Games and Complete Problems
cites work: Q4778268
cites work: Transformational methods and their application to complexity problems. Corrigenda
cites work: Q3885190
cites work: A note on two-way nondeterministic pushdown automata
cites work: Relating refined space complexity classes
cites work: Provably Difficult Combinatorial Games
cites work: On tape-bounded complexity classes and multihead finite automata
cites work: Q4140411
cites work: Q4142695
cites work: Q4146255
cites work: k + 1 Heads Are Better than k
description: scientific article; zbMATH DE number 4088958