The Power of Alternating One-Reversal Counters and Stacks

DOI10.1137/0220018MaRDI QIDQ3210175zbMATH OpenOpenAlexFDO

Authors Oscar H. Ibarra, Tao Jiang

Publication date 1991

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0220018

zbMATH Keywords

alternationcomputational complexitycounter machinepushdown automatarecursively enumerable setreversalsTuring machine

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Formal languages and automata (68Q45)

Recommendations

• Alternating multicounter machines with constant number of reversals
• One-reversal counter machines and multihead automata: revisited
• Pushdown automata with reversal-bounded counters
• One-reversal counter machines and multihead automata: revisited
• scientific article; zbMATH DE number 3982518

Cited in

(12)

• Alternating multicounter machines with constant number of reversals
• On the intersection of stacks and queues
• A characterization of exponential-time languages by alternating context- free grammars
• A note on simple programs with two variables
• Grammatical characterizations of NPDAs and VPDAs with counters
• One-reversal counter machines and multihead automata: revisited
• scientific article; zbMATH DE number 3885308 (Why is no real title available?)
• scientific article; zbMATH DE number 3961009 (Why is no real title available?)
• On the power of 1-tape off-line ATMs running in a bounded number of reversals
• Reversals and alternation
• One-reversal counter machines and multihead automata: revisited
• A note on real-time one-way alternating multicounter machines

This page was built for publication: The Power of Alternating One-Reversal Counters and Stacks

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