1999 | OriginalPaper | Buchkapitel
Complexity Classes and Rewrite Systems with Polynomial Interpretation
verfasst von : G. Bonfante, A. Cichon, J. Y Marion, H. Touzet
Erschienen in: Computer Science Logic
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.