Abstract
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 Rodriguez
We 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.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
J.M. Autebert, J. Beauquier, L. Boasson, M. Nivat, "Quelques problemes ouverts en theorie des langages algebriques" R.A.I.R.O. Theoretical Informatics 13, (1979), 363–379.
J. Berstel, "Transductions and Context-Free Languages" Teubner, Stuttgart (1979).
R.V. Book, S.A. Greibach, C. Wrathall, "Reset machines", J. Comput. System Sci. 19 (1979), 256–276.
F.J. Brandenburg, "Multiple equality sets and Post machines", J. Comput. System Sci. 21, (1980), 292–316.
F.J. Brandenburg, "Analogies of PAL and COPY", Proc. FCT 81, LNCS 117 (1981), 61–70.
S. Ginsburg, "Algebraic and Automata-theoretic Properties of Formal Languages North-Holland, Amsterdam (1975).
S.A. Greibach, "One counter languages and the chevron operation", RAIRO Theoretical Informatics 13, (1979), 189–194.
F. Rodriguez, "Families de langages fermees par crochet ouvert," Theoret. Comp. Sci. 9, (1979), 385–398.
J. S. Ullian, "Three theorems concerning principal AFLs", J. Comput. Systems Sci. 5, (1971), 304–314.
K. Wagner, "On the intersection of the class of linear context-free languages and the class of single-reset languages", Inform. Proc. Letters (to appear).
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1986 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Brandenburg, F.J. (1986). Intersections of some families of languages. In: Kott, L. (eds) Automata, Languages and Programming. ICALP 1986. Lecture Notes in Computer Science, vol 226. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-16761-7_55
Download citation
DOI: https://doi.org/10.1007/3-540-16761-7_55
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-16761-7
Online ISBN: 978-3-540-39859-2
eBook Packages: Springer Book Archive