33 citations · 206 across the 29 of their papers we have counts for
6 papers · 1 filter
Runtime Complexity Analysis of Logically Constrained Rewriting
Sarah Winkler, Georg Moser
Logically constrained rewrite systems (LCTRSs) are a versatile and efficient rewriting formalism that can be used to model programs from various programming paradigms, as well as s…
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…