On the intersection of stacks and queues (Q1123639): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0304-3975(88)90019-9 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2059530928 / rank | |||
Normal rank |
Revision as of 21:56, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the intersection of stacks and queues |
scientific article |
Statements
On the intersection of stacks and queues (English)
0 references
1988
0 references
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.
0 references
stack
0 references
pushdown
0 references
reset
0 references
counter
0 references
queue
0 references