Characterizations of PTIME, PSPACE, the polynomial hierarchy and its elements are given, which are decidable (membership can be decided by syntactic inspection to the constructions), predicative (according to points of view by Leivant and others), and are obtained by means of increasing restrictions to course-of-values recursion on trees (represented in a dialect of Lisp). (C) 2001 Elsevier Science B.V. All rights reserved.
A predicative and decidable characterization of the polynomial classes of languages / S., Caporaso; M., Zito; Galesi, Nicola. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 250:1-2(2001), pp. 83-99. [10.1016/s0304-3975(99)00116-4]
A predicative and decidable characterization of the polynomial classes of languages
GALESI, NICOLA
2001
Abstract
Characterizations of PTIME, PSPACE, the polynomial hierarchy and its elements are given, which are decidable (membership can be decided by syntactic inspection to the constructions), predicative (according to points of view by Leivant and others), and are obtained by means of increasing restrictions to course-of-values recursion on trees (represented in a dialect of Lisp). (C) 2001 Elsevier Science B.V. All rights reserved.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
