A note on undecidable properties of formal languages. (English) Zbl 0157.01902


Full Text: DOI


[1] Y. Bar-Hillel, M. Perles andE. Shamir, On formal properties of simple phrase structure grammars.Z. Phonetik Sprachwiss. Kommunikat. 14 (1961), 143–172. · Zbl 0106.34501
[2] S. Ginsburg,The Mathematical Theory of Context-Free Languages. McGraw-Hill Book Company, New York, 1966. · Zbl 0184.28401
[3] S. Ginsburg andS. Greibach, Deterministic context-free languages.Information and Control 9 (1966), 620–648. · Zbl 0145.00802 · doi:10.1016/S0019-9958(66)80019-0
[4] S. Ginsburg andS. Greibach, Abstract families of languages. SDC Document TM-738/031/00, April 1967. · Zbl 0308.68058
[5] S. Ginsburg, S. Greibach andM. Harrison, One-way stack automata.J. Assoc. Comput. Mach. 14 (1967), 389–418. · Zbl 0171.14803
[6] S. Ginsburg andE. H. Spanier, Bounded ALGOL-like languages.Trans. Amer. Math. Soc. 113 (1964), 333–368. · Zbl 0142.24803
[7] S. Ginsburg andJ. S. Ullian, Ambiguity in context-free languages.J. Assoc. Comput. Mach. 13 (1966), 62–89. · Zbl 0139.12207
[8] S. Greibach, The unsolvability of the recognition of linear context-free languages.J. Assoc. Comput. Mach. 13 (1966), 582–587. · Zbl 0148.00901
[9] J. Hopcroft andJ. Ullman, An approach to a unified theory of automata. (To appear inBell System Tech. J.)
[10] S. Rabin andD. Scott, Finite automata and their decision problems.IBM J. Res. Develop. 3 (1959), 114–125. · Zbl 0158.25404 · doi:10.1147/rd.32.0114
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.