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

computational complexityreversalspushdown automataTuring machinerecursively enumerable setcounter machinealternation

Mathematics Subject Classification ID

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

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

(11)

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

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)