×

Complexity classes and rewrite systems with polynomial interpretation. (English) Zbl 0934.03052

Gottlob, Georg (ed.) et al., Computer science logic. 12th international workshop, CSL ’98, annual conference of the EACSL, Brno, Czech Republic, August 24-28, 1998. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1584, 372-384 (1999).
Summary: We are concerned with functions over words which are computable by means of a rewrite system admitting polynomial interpretation termination proofs. We classify them according to the interpretations of successor symbols. This leads to the definition of three classes, which turn out to be exactly the poly-time, linear exponential-time and doubly linear exponential time computable functions. As a consequence, we also characterize the linear space computable functions.
For the entire collection see [Zbl 0913.00028].

MSC:

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