Limiting characterizations of low level space complexity classes
Angelaccio, Michèle ; Protasi, Marco
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 27 (1993), p. 175-182 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1993-01-01
@article{ITA_1993__27_3_175_0,
     author = {Angelaccio, Mich\`ele and Protasi, Marco},
     title = {Limiting characterizations of low level space complexity classes},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {27},
     year = {1993},
     pages = {175-182},
     mrnumber = {1227942},
     zbl = {0785.68037},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1993__27_3_175_0}
}

Angelaccio, Michèle; Protasi, Marco. Limiting characterizations of low level space complexity classes. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 27 (1993) pp. 175-182. http://gdmltest.u-ga.fr/item/ITA_1993__27_3_175_0/

[AP90] G. Ausiello and M. Protasi, Limiting polynomial approximation of complexity classes, Inter. J. Found. Comp. Sci., 1, 1990, pp. 111-122. | MR 1079444 | Zbl 0726.68030

[APA91] G. Ausiello, M. Protasi and Angelaccio, A characterization of space complexity classes and subexponential time classes as limiting polynomially decidable sets, Tech. Rep., 91-46, International Computer Science Institute, Berkeley, 1991.

[GJ79] M. R. Garey and D. S. Johnson, Computers and intractability. A guide to the theory of NP-completeness, Freeman, 1979. | MR 519066 | Zbl 0411.68039

[G65] E. M. Gold, Limiting recursion, J. Symb. Log., 30, 1965, pp. 28-45. | MR 239972 | Zbl 0203.01201

[P65] H. Putnam, Trial and error predicates and the solution to a problem of Mostowski's, J. Symb. Log., 30, 1965, pp. 48-57. | MR 195725 | Zbl 0193.30102

[S77] L. J. Stockmeyer, The polynomial-time hierarchy, Theor. Comp. Sci., 3, 1977, pp. 1-22. | MR 438810 | Zbl 0353.02024

[SM73] L. J. Stockmeyer and A. R. Meyer, Words problems requiring exponential time, Proc. 5th Ann. ACM Symp. on Th. of Comp., New York, 1973, pp. 1-9. | MR 418518 | Zbl 0359.68050

[WW85] K. Wagner and G. Wechsung, Computational Complexity, Reidel, 1985. | MR 831432 | Zbl 0584.68061