On the intersection of stacks and queues
type: Item
instance of: scholarly article
title: On the intersection of stacks and queues
zbMATH Open document ID: 0677.68088
DOI: 10.1016/0304-3975(88)90019-9
published in: Theoretical Computer Science
publication date: 1988-01-01T00:00:00Z
review text: The author establishes numerous strict inclusions and incomparabilities between the families of one-reversal one-counter, restricted one-counter, one-counter, linear context-free, single-reset, context-free, and queue languages, and various intersections of them. In fact, fourteen families are involved in a lattice presented in the paper. We mention some of the results. By a clever choice of bounded languages it is shown that (1) \({\mathcal M}(PAL)\cap {\mathcal M}(COPY)\) contains a language not in \({\mathcal M}(C)\) where \(C=(D_ 1c)^*\); (2) \({\mathcal M}(PAL)\cap {\mathcal M}(D_ 1)\) contains a language not in \({\mathcal M}(COPY)\); (3) \({\mathcal M}(COPY)\cap {\mathcal M}(D_ 1)\) contains a language not in \({\mathcal M}(PAL)\); (4) \({\mathcal M}(S)\) is strictly included in \({\mathcal M}(PAL)\cap {\mathcal M}(COPY)\cap {\mathcal M}(D_ 1)\) where S consists of all words \(a^ nb^ n\). These results disprove conjectures presented by several authors about ten years ago.
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 4110152
zbMATH Keywords: stack
zbMATH Keywords: pushdown
zbMATH Keywords: reset
zbMATH Keywords: counter
zbMATH Keywords: queue
author: Franz J. Brandenburg
reviewed by: Paavo Turakainen
MaRDI profile type: Publication
full work available at URL: 0304-3975(88)90019-9
OpenAlex ID: W2059530928
cites work: Q3873564
cites work: Q3859267
cites work: Reset machines
cites work: Multiple equality sets and Post machines
cites work: Three write heads are as good ask
cites work: Q3912052
cites work: Q3730030
cites work: Q4089754
cites work: Q3883536
cites work: Single-tape reset machines
cites work: Familles de langages fermées par crochet ouvert
cites work: Three theorems concerning principal AFLs
cites work: Automates a file
cites work: On the intersection of the class of linear context-free languages and the class of single-reset languages
description: scientific article; zbMATH DE number 4110152