Alternating multihead finite automata

DOI10.1016/0304-3975(88)90122-3zbMath0665.68064OpenAlexW2061631274MaRDI QIDQ1116353

K. N. King

Publication date: 1988

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(88)90122-3

zbMATH Keywords

alternating Turing machinealternating multihead finite automatadeterministic time and space complexitymultihead pushdown automatanondeterministic multihead finite automata

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05)

Related Items

Deterministic versus nondeterministic space in terms of synchronized alternating machines, On communication-bounded synchronized alternating finite automata, Refined simulation of multihead automata, Some results concerning two-dimensional turing machines and finite automata, Low complexity classes of multidimensional cellular automata, Tradeoffs for language recognition on alternating machines, A communication hierarchy of parallel computations, Three-dimensional alternating Turing machines with only universal states, The complexity of debate checking, Multihead two-way probabilistic finite automata, Alternation in simple devices, On space-bounded synchronized alternating Turing machines, Alternation for sublogarithmic space-bounded alternating pushdown automata, Properties of probabilistic pushdown automata, Multihead two-way probabilistic finite automata, Properties of probabilistic pushdown automata, 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, On the power of synchronization in parallel computations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two-way nondeterministic pushdown automata
• On tape-bounded complexity classes and multihead finite automata
• An observation on time-storage trade off
• Space-bounded reducibility among combinatorial problems
• Relating refined space complexity classes
• Complete problems for deterministic polynomial time
• Transformational methods and their application to complexity problems. Corrigenda
• Propositional dynamic logic of regular programs
• On non-determinacy in simple computing devices
• Pushdown automata with counters
• On two-way multihead automata
• Provably Difficult Combinatorial Games
• Classes of Pebble Games and Complete Problems
• Alternation
• Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages
• k + 1 Heads Are Better than k
• Multi-tape and multi-head pushdown automata
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• Time and tape complexity of pushdown automaton languages