Deprecated: $wgMWOAuthSharedUserIDs=false is deprecated, set $wgMWOAuthSharedUserIDs=true, $wgMWOAuthSharedUserSource='local' instead [Called from MediaWiki\HookContainer\HookContainer::run in /var/www/html/w/includes/HookContainer/HookContainer.php at line 135] in /var/www/html/w/includes/Debug/MWDebug.php on line 372
The Power of Alternating One-Reversal Counters and Stacks - MaRDI portal

The Power of Alternating One-Reversal Counters and Stacks

From MaRDI portal

Publication:3210175

Jump to:navigation, search

DOI10.1137/0220018zbMath0722.68054OpenAlexW1973956010MaRDI QIDQ3210175

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 complexity Turing machine recursively enumerable set alternation reversals pushdown automata counter machine

Mathematics Subject Classification ID

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

Related Items (3)

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

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

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:3210175&oldid=16385594"