A characterization of polynomial complexity classes using dependency pairs

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