The Power of Alternating One-Reversal Counters and Stacks

DOI10.1137/0220018zbMATH Open0722.68054OpenAlexW1973956010MaRDI QIDQ3210175FDOQ3210175

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)

Cited In (3)

• A characterization of exponential-time languages by alternating context- free grammars
• On the power of 1-tape off-line ATMs running in a bounded number of reversals
• A note on simple programs with two variables

   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 👍 👎
• Title not available (Why is that?) 👍 👎

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)