Abstract
The Boolean closure of the deterministic context-free languages is properly contained in the intersection-closure of the context-free languages and the latter is properly contained in the Boolean closure of the context-free languages. The class of context-free languages and the Boolean closure of the deterministic context-free languages are incomparable in the sense that neither one is contained in the other. The intersection-closures of the deterministic and nondeterministic context-free languages are not principal AFDL’s.
The research in this paper was supported in part by the National Science Foundation under Grant GJ-803.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
Book, R.V. and Greibach, S.A., “Quasi-Realtime Languages”, Mathematical Systems Theory, 4 (1970), 97–111.
Chandler, W.J., “Abstract Families of Deterministic Languages”, SDC Technical Report, TM-738/052/00, Santa Monica, California, (1969).
Cole, S.N., “Deterministic Pushdown Store Machines and Real-Time Computation”, JACM, 18 (1971), 306–328.
Ginsburg, S., The Mathematical Theory of Context-Free Languages, McGraw-Hill, New York, (1966).
Ginsburg, S. and Greibach, S.A., “Deterministic Context-Free Languages”, Information and Control, 9 (1966), 602–648.
Greibach, S.A., “Jump PDA’s, Deterministic Context-Free Languages, Principal AFDL’s and Polynomial Time Recognition”, Proceedings of Fifth Annual ACM Symposium on Theory of ComRuting, Austin, Texas, 1973, 20–28.
Knuth, D.E., “On the Tranlation of Languages from Left to Right”, Information and Control, 8 (1965), 607–639.
Liu, L.Y. and Weiner, P., “An Infinite Hierarchy of Intersectionsof Context-Free Languages”, Mathematical Systems Theory, 7 (1973).
Wotschke, D., “A Characterisation of Boolean Closures of Families of Languages”, will appear in Lecture Notes in Computer Science, Springer-Verlag, New York, (1973).
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1973 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Wotschke, D. (1973). The Boolean Closures of the Deterministic and Nondeterministic Context-Free Languages. In: Brauer, W. (eds) GI Gesellschaft für Informatik e. V.. Lecture Notes in Computer Science, vol 1. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-41148-3_11
Download citation
DOI: https://doi.org/10.1007/978-3-662-41148-3_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-40668-7
Online ISBN: 978-3-662-41148-3
eBook Packages: Springer Book Archive