A characterization of reversal-bounded multipushdown machine languages

DOI10.1016/0304-3975(85)90052-0MaRDI QIDQ1058865zbMATH OpenOpenAlexFDO

Authors Wojciech Rytter, Marek Chrobak

Publication date 1985

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(85)90052-0

zbMATH Keywords

deterministic reversal-bounded multipushdown machinesDLOG

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Review text

We prove that DLOG is equal to the class of languages recognized by deterministic reversal-bounded multipushdown machines.

Cites work

• A note on bounded-reversal multipushdown machines
• Note on tape reversal complexity of languages
• On reversal-bounded counter machines and on pushdown automata with a bound on the size of the pushdown store
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• Reversal-bounded multipushdown machines
• Simple counter machines and number-theoretic problems
• Tape-reversal bounded Turing machine computations
• The reduction of tape reversals for off-line one-tape Turing machines

Cited in

(1)

• On reversal bounded alternating Turing machines

This page was built for publication: A characterization of reversal-bounded multipushdown machine languages

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