Alternating multihead finite automata
From MaRDI portal
Recommendations
Cites work
- 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?)
- 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
- 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
Cited in
(32)- Remarks on multihead pushdown automata and multihead stack automata
- Some results concerning two-dimensional turing machines and finite automata
- On space-bounded synchronized alternating Turing machines
- The complexity of debate checking
- Deterministic versus nondeterministic space in terms of synchronized alternating machines
- Alternating simple multihead finite automata
- Low complexity classes of multidimensional cellular automata
- Alternating multicounter machines with constant number of reversals
- On the power of alternation in automata theory
- Multihead two-way probabilistic finite automata
- scientific article; zbMATH DE number 3868618 (Why is no real title available?)
- Multi-head finite automata: characterizations, concepts and open problems
- Finite dP Automata versus Multi-head Finite Automata
- An alternating hierarchy for finite automata
- Multihead two-way probabilistic finite automata (extended abstract)
- A communication hierarchy of parallel computations
- Three-dimensional alternating Turing machines with only universal states
- Tradeoffs for language recognition on alternating machines
- Properties of probabilistic pushdown automata
- Constructions for alternating finite automata∗
- A NOTE ON MULTIHEAD FINITE-STATE AUTOMATA
- scientific article; zbMATH DE number 4094826 (Why is no real title available?)
- Possibilities of various types of alternating automata
- Alternation in simple devices
- On the power of synchronization in parallel computations
- Some characterizations of multihead finite automata
- scientific article; zbMATH DE number 1088283 (Why is no real title available?)
- Properties of probabilistic pushdown automata
- On communication-bounded synchronized alternating finite automata
- Refined simulation of multihead automata
- Alternation for sublogarithmic space-bounded alternating pushdown automata
- scientific article; zbMATH DE number 3980491 (Why is no real title available?)
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)
