Skip to Main content Skip to Navigation
Reports

A characterization of polynomial complexity classes using dependency pairs

Jean-Yves Marion 1 Romain Péchoux 1
1 CARTE - Theoretical adverse computations, and safety
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : The dependency pair method has already shown its power in proving termination of term rewriting systems. We adapt this framework using polynomial assignments in order to characterize with two distinct criteria the set of the functions computable in polynomial time and the set of the functions computable in polynomial space. To our knowledge, this is a first attempt to capture complexity classes using of the dependency pair method. The characterizations presented are inspired by previous works on implicit computational complexity, and, particularly, by the notions of quasi-interpretation and sup-interpretation. Both criteria are decidable so that we can synthesize resource upper-bounds.
Complete list of metadatas

Cited literature [19 references]  Display  Hide  Download

https://hal.inria.fr/inria-00155287
Contributor : Romain Péchoux <>
Submitted on : Sunday, June 17, 2007 - 6:39:24 PM
Last modification on : Tuesday, December 18, 2018 - 4:48:02 PM
Document(s) archivé(s) le : Thursday, April 8, 2010 - 8:32:17 PM

File

dependency.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00155287, version 1

Collections

Citation

Jean-Yves Marion, Romain Péchoux. A characterization of polynomial complexity classes using dependency pairs. [Research Report] 2007, pp.12. ⟨inria-00155287⟩

Share

Metrics

Record views

217

Files downloads

115