Georg Moser
A New Order-theoretic Characterisation of the Polytime Computable Functions.
Fri, 01/13/2012 - 15:01 — SomNambulAuthors: Martin Avanzini, Georg Moser, Naohi Eguchi
Subjects: Computational Complexity
AbstractWe 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 rewrite systems. Any polynomial time computable
function gives rise to a rewrite system that is compatible with sPOP*. On the
other hand any function defined by a rewrite system compatible with sPOP* is
polynomial time computable. Technically sPOP* is a tamed recursive path order
with product status.Termination Proofs in the Dependency Pair Framework May Induce Multiple Recursive Derivational Complexity.
Tue, 03/29/2011 - 15:01 — SomNambulAuthors: Georg Moser, Andreas Schnabl
Subjects: Logic in Computer Science
AbstractWe study the derivational complexity of rewrite systems whose termination is
provable in the dependency pair framework using the processors for reduction
pairs, dependency graphs, or the subterm criterion. We show that the
derivational complexity of such systems is bounded by a multiple recursive
function, provided the derivational complexity induced by the employed base
techniques is at most multiple recursive. Moreover we show that this upper
bound is tight.Efficient Implementation of Rewriting Revisited Technical Report.
Mon, 02/01/2010 - 16:01 — SomNambulAuthors: Martin Avanzini, Georg Moser
Subjects: Computational Complexity
AbstractRecently, 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 authors have shown that for confluent TRSs,
innermost polynomial runtime complexity induces polytime computability of the
functions defined.
User login
