Limiting characterizations of low level space complexity classes

Michèle Angelaccio; Marco Protasi

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1993)

  • Volume: 27, Issue: 3, page 175-182
  • ISSN: 0988-3754

How to cite

top

Angelaccio, Michèle, and Protasi, Marco. "Limiting characterizations of low level space complexity classes." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 27.3 (1993): 175-182. <http://eudml.org/doc/92447>.

@article{Angelaccio1993,
author = {Angelaccio, Michèle, Protasi, Marco},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {limiting recursion; complexity theory; space complexity classes},
language = {eng},
number = {3},
pages = {175-182},
publisher = {EDP-Sciences},
title = {Limiting characterizations of low level space complexity classes},
url = {http://eudml.org/doc/92447},
volume = {27},
year = {1993},
}

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
PB - EDP-Sciences
VL - 27
IS - 3
SP - 175
EP - 182
LA - eng
KW - limiting recursion; complexity theory; space complexity classes
UR - http://eudml.org/doc/92447
ER -

References

top
  1. [AP90] G. AUSIELLO and M. PROTASI, Limiting polynomial approximation of complexity classes, Inter. J. Found. Comp. Sci., 1, 1990, pp. 111-122. Zbl0726.68030MR1079444
  2. [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. 
  3. [GJ79] M. R. GAREY and D. S. JOHNSON, Computers and intractability. A guide to the theory of NP-completeness, Freeman, 1979. Zbl0411.68039MR519066
  4. [G65] E. M. GOLD, Limiting recursion, J. Symb. Log., 30, 1965, pp. 28-45. Zbl0203.01201MR239972
  5. [P65] H. PUTNAM, Trial and error predicates and the solution to a problem of Mostowski's, J. Symb. Log., 30, 1965, pp. 48-57. Zbl0193.30102MR195725
  6. [S77] L. J. STOCKMEYER, The polynomial-time hierarchy, Theor. Comp. Sci., 3, 1977, pp. 1-22. Zbl0353.02024MR438810
  7. [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. Zbl0359.68050MR418518
  8. [WW85] K. WAGNER and G. WECHSUNG, Computational Complexity, Reidel, 1985. Zbl0584.68061MR831432

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.