23 citations · 74 across the 18 of their papers we have counts for
6 papers · 1 filter
On Sharing, Memoization, and Polynomial Time (Long Version)
Martin Avanzini, Ugo Dal Lago
We study how the adoption of an evaluation mechanism with sharing and memoization impacts the class of functions which can be computed in polynomial time. We first show how a natur…
A Combination Framework for Complexity
Martin Avanzini, Georg Moser
In this paper we present a combination framework for polynomial complexity analysis of term rewrite systems. The framework covers both derivational and runtime complexity analysis.…
Polynomial Path Orders: A Maximal Model
Martin Avanzini, Georg Moser
This paper is concerned with the automated complexity analysis of term rewrite systems (TRSs for short) and the ramification of these in implicit computational complexity theory (I…
A New Order-theoretic Characterisation of the Polytime Computable Functions
Martin Avanzini, Naohi Eguchi, Georg Moser
We propose a new order, the small polynomial path order (sPOP* for short). The order sPOP* provides a characterisation of the class of polynomial time computable function via term…
A Path Order for Rewrite Systems that Compute Exponential Time Functions (Technical Report)
Martin Avanzini, Naohi Eguchi, Georg Moser
In this paper we present a new path order for rewrite systems, the exponential path order EPOSTAR. Suppose a term rewrite system is compatible with EPOSTAR, then the runtime comple…
Efficient Implementation of Rewriting Revisited Technical Report
Martin Avanzini, Georg Moser
Recently, many techniques have been introduced that allow the (automated) classification of the runtime complexity of term rewrite systems (TRSs for short). In earlier work, the au…