Limiting characterizations of low level space complexity classes
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 27 (1993) no. 3, pp. 175-182.
@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},
     pages = {175--182},
     publisher = {EDP-Sciences},
     volume = {27},
     number = {3},
     year = {1993},
     zbl = {0785.68037},
     mrnumber = {1227942},
     language = {en},
     url = {http://www.numdam.org/item/ITA_1993__27_3_175_0/}
}
TY  - JOUR
AU  - Angelaccio, Michèle
AU  - Protasi, Marco
TI  - Limiting characterizations of low level space complexity classes
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1993
DA  - 1993///
SP  - 175
EP  - 182
VL  - 27
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_1993__27_3_175_0/
UR  - https://zbmath.org/?q=an%3A0785.68037
UR  - https://www.ams.org/mathscinet-getitem?mr=1227942
LA  - en
ID  - ITA_1993__27_3_175_0
ER  - 
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) no. 3, pp. 175-182. http://www.numdam.org/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