Geodesic
A note on the undecidability of contextfreeness
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 16 (1982) no. 1, pp. 3-11.

Voir la notice de l'article provenant de la source Numdam

@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},
     pages = {3--11},
     publisher = {EDP-Sciences},
     volume = {16},
     number = {1},
     year = {1982},
     mrnumber = {677652},
     zbl = {0493.68078},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ITA_1982__16_1_3_0/}
}
TY  - JOUR
AU  - Albert, J.
TI  - A note on the undecidability of contextfreeness
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1982
SP  - 3
EP  - 11
VL  - 16
IS  - 1
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/item/ITA_1982__16_1_3_0/
LA  - en
ID  - ITA_1982__16_1_3_0
ER  - 
%0 Journal Article
%A Albert, J.
%T A note on the undecidability of contextfreeness
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 1982
%P 3-11
%V 16
%N 1
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/item/ITA_1982__16_1_3_0/
%G en
%F 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) no. 1, pp. 3-11. http://geodesic.mathdoc.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. | Zbl | MR

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. | Zbl | MR

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

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. | Zbl | MR

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. | Zbl | MR

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. | Zbl | MR

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. | Zbl | MR

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. | Zbl | MR

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

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

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

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

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

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

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