Skip to main content

1986 | ReviewPaper | Buchkapitel

Intersections of some families of languages

verfasst von : Franz J. Brandenburg

Erschienen in: Automata, Languages and Programming

Verlag: Springer Berlin Heidelberg

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

What do a pushdown and a queue have in common? What is their intersection? Is it a counter? If we add the one-reversal restriction, is a one-reversal counter exactly the intersection of a one-reversal pushdown and a queue or, symmetrically, the intersection of a one-reset tape and a pushdown? These and similar assumptions can be heard here and there, and there are some conjectures by Autebert et al. [1], Book et al. [3] and RodriguezWe disprove all these conjectures 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, we obtain new families of languages from intersections of some well-known families.

Metadaten
Titel
Intersections of some families of languages
verfasst von
Franz J. Brandenburg
Copyright-Jahr
1986
Verlag
Springer Berlin Heidelberg
DOI
https://doi.org/10.1007/3-540-16761-7_55