×

zbMATH — the first resource for mathematics

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

Software:
ALGOL 60
PDF BibTeX XML Cite
Full Text: DOI
References:
[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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.