Alternating multihead finite automata
[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.
- k + 1 Heads Are Better than k
- A note on two-way nondeterministic pushdown automata
- Alternation
- An observation on time-storage trade off
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
- Classes of Pebble Games and Complete Problems
- Complete problems for deterministic polynomial time
- scientific article; zbMATH DE number 3690693 (Why is no real title available?)
- scientific article; zbMATH DE number 3569860 (Why is no real title available?)
- scientific article; zbMATH DE number 3571498 (Why is no real title available?)
- scientific article; zbMATH DE number 3576701 (Why is no real title available?)
- scientific article; zbMATH DE number 3639163 (Why is no real title available?)
- scientific article; zbMATH DE number 3454792 (Why is no real title available?)
- scientific article; zbMATH DE number 3403734 (Why is no real title available?)
- Multi-tape and multi-head pushdown automata
- On non-determinacy in simple computing devices
- On tape-bounded complexity classes and multihead finite automata
- On two-way multihead automata
- Propositional dynamic logic of regular programs
- Provably Difficult Combinatorial Games
- Pushdown automata with counters
- Relating refined space complexity classes
- Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages
- Space-bounded reducibility among combinatorial problems
- Time and tape complexity of pushdown automaton languages
- Transformational methods and their application to complexity problems. Corrigenda
- Remarks on multihead pushdown automata and multihead stack automata
- Alternating simple multihead finite automata
- Alternating multicounter machines with constant number of reversals
- On the power of alternation in automata theory
- Tradeoffs for language recognition on alternating machines
- A communication hierarchy of parallel computations
- Three-dimensional alternating Turing machines with only universal states
- On space-bounded synchronized alternating Turing machines
- Properties of probabilistic pushdown automata
- Deterministic versus nondeterministic space in terms of synchronized alternating machines
- On communication-bounded synchronized alternating finite automata
- Refined simulation of multihead automata
- Finite dP Automata versus Multi-head Finite Automata
- A NOTE ON MULTIHEAD FINITE-STATE AUTOMATA
- scientific article; zbMATH DE number 3868618 (Why is no real title available?)
- Constructions for alternating finite automata∗
- Some characterizations of multihead finite automata
- scientific article; zbMATH DE number 3980491 (Why is no real title available?)
- Possibilities of various types of alternating automata
- scientific article; zbMATH DE number 4094826 (Why is no real title available?)
- scientific article; zbMATH DE number 29610 (Why is no real title available?)
- scientific article; zbMATH DE number 30303 (Why is no real title available?)
- scientific article; zbMATH DE number 1088283 (Why is no real title available?)
- An alternating hierarchy for finite automata
- Alternation in simple devices
- The complexity of debate checking
- Properties of probabilistic pushdown automata
- Some results concerning two-dimensional turing machines and finite automata
- Multihead two-way probabilistic finite automata (extended abstract)
- Multi-head finite automata: characterizations, concepts and open problems
- Alternation for sublogarithmic space-bounded alternating pushdown automata
- Multihead two-way probabilistic finite automata
- FC-Datalog as a framework for efficient string querying
- On the power of synchronization in parallel computations
- Low complexity classes of multidimensional cellular automata
This page was built for publication: Alternating multihead finite automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1116353)
