The Power of Alternating One-Reversal Counters and Stacks

DOI10.1137/0220018zbMATH Open0722.68054OpenAlexW1973956010MaRDI QIDQ3210175FDOQ3210175

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

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

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)

Cited In (11)

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

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)