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

(12)

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

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)