On the intersection of stacks and queues

https://doi.org/10.1016/0304-3975(88)90019-9Get rights and content
Under an Elsevier user license
open archive

Abstract

What do a pushdown stack and a queue have in common? What is their intersection? Is it a counter? If we add a retrieval restriction, what is the intersection of a one-reversal pushdown and a queue, or, by symmetry, of a one-reset tape and a pushdown, or both, a one-reversal pushdown and a one-reset queue? Is it a one-reversal counter? These and similar claims are conjectured by Autebert et al. (1979), Book et al. (1979), and Rodriguez (1979).

We approach these problems in terms of families of languages defined by nondeterministic real-time machines whose storage tape is a pushdown stack, a queue and a counter respectively. We disprove all conjectures from above and show that counters are strictly weaker than the intersection of pushdowns and queues. This goes through for the restriction to one-reversal or one-reset. In fact, there is a complete lattice of new families of languages between the regular languages and the context-free languages, obtained by the intersection of the families of languages that are defined by machines with a pushdown, a queue and a counter, and their one-reversal restrictions respectively.

Cited by (0)