A note on the undecidability of contextfreeness
Albert, J.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 16 (1982), p. 3-11 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1982-01-01
@article{ITA_1982__16_1_3_0,
     author = {Albert, J.},
     title = {A note on the undecidability of contextfreeness},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {16},
     year = {1982},
     pages = {3-11},
     mrnumber = {677652},
     zbl = {0493.68078},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1982__16_1_3_0}
}

Albert, J. A note on the undecidability of contextfreeness. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 16 (1982) pp. 3-11. http://gdmltest.u-ga.fr/item/ITA_1982__16_1_3_0/

1. A.V. Aho, Indexed Grammars - an Extension of Context - Free Grammars, J. Assoc. Comput. Mach., Vol. 15, 1968, pp. 647-671. | MR 258547 | Zbl 0175.27801

2. J. Albert, Über indizierte und m-Block-indizierte Grammatiken, Ph. D. Thesis, Institut fur Angewandte Informatik und Formale Beschreibungsverfahren, Univ. Karlsruhe, 1976.

3. J. Albert and L. Wegner, Languages with Homomorphic Replacements, Theor. Comput. Sc., Vol. 16, 1981, pp. 291-305. | MR 642323 | Zbl 0468.68085

4. P. Asveld and J. Engelfriet, Iterated Deterministic Substitution, Acta Informatica, Vol. 8, 1977, pp. 285-302. | MR 478764 | Zbl 0343.68034

5. J.-M. Autebert, J. Beauquier, L. Boasson and M. Latteux, Indécidabilité de la condition IRS, Université de Lille I, publication n° 18.79, 1979.

6. B. S. Baker and R. V. Book, Reversal-Bounded Multipush-down Machines, J. Comput. System Sci., Vol. 8, 1974, pp. 315-332. | MR 375844 | Zbl 0309.68043

7. Y. Bar-Hillel, M. Perles and E. Shamir, On Formal Properties of Simple Phrase-Structure Grammars, Z. f. Phonetik, Sprachwissenschaft, Kommunikations-forschung, Vol. 14, 1961, pp. 143-177. | MR 151376 | Zbl 0106.34501

8. J. Engelfriet, E. Meineche Schmidt and J. Van Leeuwen, Stack Machines and Classes of Nonnested Macro Languages, J. Assoc. Comput. Mach., Vol.27, 1980, pp. 96-117. | MR 554283 | Zbl 0428.68087

9. M. J. Fischer, Grammars with Macro-like Productions, Ph. D. Thesis, Haryard Univ., Cambridge, Mass., 1968.

10. S. Ginsburg and H. G. Rice, Two Families of Languages Related to ALGOL, J. Assoc. Comput. Mach., Vol. 9, 1962, pp. 350-371. | MR 152158 | Zbl 0196.01803

11. S. Ginsburg, Formal Languages, North-Holland, Amsterdam, 1975.

12. S. Greibach, A Note on Undecidable Properties of Formal Languages, Math. Systems Theory, Vol. 2, 1968, pp. 1-6. | MR 225609 | Zbl 0157.01902

13. S. Greibach, An Infinite Hierarchy of Context-Free Languages, J. Assoc. Comput. Mach., Vol. 16, 1969, pp. 9-106. | MR 238632 | Zbl 0182.02002

14. S. Greibach, Checking Automata andone-way Stack Languages, J. Comput. System Sc., Vol.3, 1969, pp. 196-217. | MR 243953 | Zbl 0174.02702

15. S. Greibach, One Way Finite Visit Automata, Theor. Comput. Sc.,Vol. 6, 1978, pp. 175-221. | MR 489039 | Zbl 0368.68059

16. M. A. Harrison, Introduction to Formal Language Theory, Addison-Wesley, Reading, Massachusetts, 1978. | MR 526397 | Zbl 0411.68058

17. D. E. Knuth, On the Translation of Languages from Left to Right, Information and Control, Vol. 8, 1965, pp. 607-635. | MR 189942 | Zbl 0231.68027

18. M. Levitina, O nekotoryh grammatikah s pravilami globalnoi podstanovki, Akad. Nauk S.S.S.R. Nauchno-Tekhn. Inform., Ser. 2, 1973, pp. 32-36. | Zbl 0291.68024

19. M. Linna, The DOL-Ness for Context-FreeLanguages is Decidable, Inf. Process. Letters, Vol. 5, 1976, pp. 149-151. | MR 451889 | Zbl 0346.68033