The Library
Syntactic characterization in Lisp of the polynomial complexity classes and hierarchy
Tools
UNSPECIFIED (1997) Syntactic characterization in Lisp of the polynomial complexity classes and hierarchy. In: 3rd Italian Conference on Algorithms and Complexity (CIAC 97), UNIV ROME LA SAPIENZA, ROME, ITALY, MAR 12-14, 1997. Published in: ALGORITHMS AND COMPLEXITY, 1203 pp. 61-73. ISBN 3-540-62592-5. ISSN 0302-9743.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Abstract
The definition of a class C of functions is syntactic if membership to C can be decided from the construction of its elements. Syntactic characterizations of PTIMEF, of PSPACEF, of the polynomial hierarchy PH, and of its subclasses Delta(n)(p) are presented. They are obtained by progressive restrictions of recursion in Lisp, and may be regarded as predicative according to a foundational point raised by Leivant.
Item Type: | Conference Item (UNSPECIFIED) | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Series Name: | LECTURE NOTES IN COMPUTER SCIENCE | ||||
Journal or Publication Title: | ALGORITHMS AND COMPLEXITY | ||||
Publisher: | SPRINGER-VERLAG BERLIN | ||||
ISBN: | 3-540-62592-5 | ||||
ISSN: | 0302-9743 | ||||
Editor: | Bongiovanni, G and Bovet, DP and diBattista, G | ||||
Official Date: | 1997 | ||||
Dates: |
|
||||
Volume: | 1203 | ||||
Number of Pages: | 13 | ||||
Page Range: | pp. 61-73 | ||||
Publication Status: | Published | ||||
Title of Event: | 3rd Italian Conference on Algorithms and Complexity (CIAC 97) | ||||
Location of Event: | UNIV ROME LA SAPIENZA, ROME, ITALY | ||||
Date(s) of Event: | MAR 12-14, 1997 |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |