scientific article; zbMATH DE number 2006637

MaRDI QIDQ4436033zbMATH OpenFDO

Authors Isabel Oitavem

Publication date 23 November 2003

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2183/21830170.htm

zbMATH Keywords

computational complexityterm rewritingimplicit characterizationsPspace

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Grammars and rewriting systems (68Q42) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• Characterizing PSPACE with pointers
• A term rewriting characterization of the functions computable in polynomial space
• On characterizations of the class PSPACE/poly
• scientific article; zbMATH DE number 5722524
• An implicit characterization of PSPACE

Cited in

(13)

• scientific article; zbMATH DE number 5722524 (Why is no real title available?)
• An implicit characterization of PSPACE
• On characterizations of the class PSPACE/poly
• Characterizing PSPACE with pointers
• Logspace without bounds
• On basic feasible functionals and the interpretation method
• A characterization of basic feasible functionals through higher-order rewriting and tuple interpretations
• Formalizing termination proofs under polynomial quasi-interpretations
• V-comprehensions and P space
• On sharing, memoization, and polynomial time
• Monotonicity constraints in characterizations of PSPACE
• An implicit characterization of the polynomial-time decidable sets by cons-free rewriting
• Separating NC along the \(\delta\) axis

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4436033)