Independent instances for some undecidable problems
Calude, Cristian ; Păun, Gheorghe
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 17 (1983), p. 49-54 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1983-01-01
@article{ITA_1983__17_1_49_0,
     author = {Calude, Cristian and P\u aUN, Gheorghe},
     title = {Independent instances for some undecidable problems},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {17},
     year = {1983},
     pages = {49-54},
     mrnumber = {701987},
     zbl = {0517.03022},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1983__17_1_49_0}
}

Calude, Cristian; Păun, Gheorghe. Independent instances for some undecidable problems. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 17 (1983) pp. 49-54. http://gdmltest.u-ga.fr/item/ITA_1983__17_1_49_0/

1. M. Davis, Yu. Matijasevič and J. Robinson, Hilbert's Tenth Problem. Diophantine Equations : Positive Aspects of a Negative Solution, Proc. Symposia Pure Math., vol. 28, 1976, p. 223-378. | MR 432534 | Zbl 0346.02026

2. S. Greibach and J. Hopcroft, Scattered Context Grammars, J. Comput. Systems Sci., vol. 3, 1969, p. 233-247. | MR 246727 | Zbl 0174.02801

3. J. Hartmanis and J. Hopcroft, Independence Results in Computer Science, ACM SIGACT News, vol. 8, 1976, p. 13-24.

4. Yu. Matijasevic, Enumerable Sets Are Diophantine. Dokl. Akad. Nauk SSSR, vol. 191, 1970, p. 279-282. | MR 258744 | Zbl 0212.33401

5. H. A. Maurer, Simple Matrix Languages with a Leftmost Restriction, Inform. Control, vol., 23, 1973, p. 128-139. | MR 388868 | Zbl 0261.68037

6. J. Paris and L. Harrington, A Mathematical Incompleteness in Peano Arithmetic, in J. Barwise (ed.), Handbook of Mathematical Logic, North-Holland, Amsterdam, 1977, p. 1133-1142. | MR 457132

7. E. Post, A Variant of a Recursively Unsolvable Problem, Bull. AMS, vol. 52, 1946, p. 264-268. | MR 15343 | Zbl 0063.06329

8. H. Jr. Rogers, Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York, 1967. | MR 224462 | Zbl 0183.01401

9. D. Rosenkrantz, Programmed Grammars and Classes of Formal Languages, J. of ACM, vol. 16, 1969, p. 107-131. | MR 235940 | Zbl 0182.02004

10. A. Salomaa, Formal Languages, Academic Press, New York, London, 1973. | MR 438755 | Zbl 0262.68025