A term rewriting characterization of the polytime functions and related complexity classes.

Arnold Beckmann Andreas Weiermann

Published in: Arch. Math. Log. (1996)

Keyphrases

term rewriting
theorem proving
tractable cases
theorem prover
complexity measures
knuth bendix
rewrite systems
computational complexity
worst case
operational semantics