A characterization of reversal-bounded multipushdown machine languages
type: Item
instance of: scholarly article
title: A characterization of reversal-bounded multipushdown machine languages
zbMATH Open document ID: 0565.68079
DOI: 10.1016/0304-3975(85)90052-0
author: Wojciech Rytter
author: Marek Chrobak
published in: Theoretical Computer Science
publication date: 1985-01-01T00:00:00Z
review text: We prove that DLOG is equal to the class of languages recognized by deterministic reversal-bounded multipushdown machines.
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 3902072
zbMATH Keywords: DLOG
zbMATH Keywords: deterministic reversal-bounded multipushdown machines
MaRDI profile type: Publication
full work available at URL: 0304-3975(85)90052-0
OpenAlex ID: W2046750655
cites work: Reversal-bounded multipushdown machines
cites work: A note on bounded-reversal multipushdown machines
cites work: On reversal-bounded counter machines and on pushdown automata with a bound on the size of the pushdown store
cites work: The reduction of tape reversals for off-line one-tape Turing machines
cites work: Simple counter machines and number-theoretic problems
cites work: Reversal-Bounded Multicounter Machines and Their Decision Problems
cites work: Tape-reversal bounded Turing machine computations
cites work: Note on tape reversal complexity of languages
cites work: Recursive unsolvability of Post's problem of ''Tag'' und other topics in theory of Turing machines
description: scientific article; zbMATH DE number 3902072