A note on bounded-reversal multipushdown machines
type: Item
instance of: scholarly article
title: A note on bounded-reversal multipushdown machines
zbMATH Open document ID: 0562.68064
DOI: 10.1016/0020-0190(84)90080-2
author: Marek Chrobak
published in: Information Processing Letters
publication date: 1984-01-01T00:00:00Z
review text: Let P(k,n) denote the class of deterministic two-way k-pushdown automata M such that the accepted language T(M) is included in \(a^*\) and M can make at most n reversals in each of its k pushdown tapes. It is shown that P(1,n) induces only regular languages T(M) but there is an automaton M in P(2,1) with T(M) not regular.
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q05
zbMATH DE Number: 3896331
zbMATH Keywords: multicounter machines
zbMATH Keywords: pushdown automata
zbMATH Keywords: regular languages
reviewed by: Tero Harju
MaRDI profile type: Publication
full work available at URL: 0020-0190(84)90080-2
OpenAlex ID: W2013634958
cites work: Reversal-bounded multipushdown machines
cites work: Simple counter machines and number-theoretic problems
cites work: A note on semilinear sets and bounded-reversal multihead pushdown automata
description: scientific article; zbMATH DE number 3896331