On input read-modes of alternating Turing machines

DOI10.1016/0304-3975(94)00253-FzbMATH Open0873.68055MaRDI QIDQ672377FDOQ672377

Authors: Liming Cai, Jianer Chen 

Publication date: 28 February 1997

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

Recommendations

• ALTERNATING TURING MACHINES WITH MODIFIED ACCEPTING STRUCTURE
• On reversal bounded alternating Turing machines
• A note on alternating on-line Turing machines
• scientific article; zbMATH DE number 1696661
• Alternating Turing machines for inductive languages
• scientific article; zbMATH DE number 4047169
• scientific article; zbMATH DE number 3885317
• Reversal Complexity Classes for Alternating Turing Machines
• On the power of alternation on reversal-bounded alternating Turing machines with a restriction
• On the Way to Alternating Weak Automata

zbMATH Keywords

Turing machine

Mathematics Subject Classification ID

Cites Work

• Optimization, approximation, and complexity classes
• On uniform circuit complexity
• On uniformity within \(NC^ 1\)
• A taxonomy of problems with fast parallel algorithms
• Title not available (Why is that?)
• Alternation
• Characterizing parallel hierarchies by reducibilities
• Parity, circuits, and the polynomial-time hierarchy
• Title not available (Why is that?)
• Title not available (Why is that?)
• An Optimal Parallel Algorithm for Formula Evaluation
• Logical definability of NP optimization problems
• Quantifiers and approximation
• Title not available (Why is that?)

Cited In (5)

• On fixed-parameter tractability and approximability of NP optimization problems
• On log-time alternating Turing machines of alternation depth k
• Alternating Turing machines for inductive languages
• ALTERNATING TURING MACHINES WITH MODIFIED ACCEPTING STRUCTURE
• Gap-languages and log-time complexity classes

This page was built for publication: On input read-modes of alternating Turing machines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q672377)