12 citations · 17 across the 11 of their papers we have counts for
4 papers · 1 filter
Complexity Analysis of Precedence Terminating Infinite Graph Rewrite Systems
Naohi Eguchi
The general form of safe recursion (or ramified recurrence) can be expressed by an infinite graph rewrite system including unfolding graph rewrite rules introduced by Dal Lago, Mar…
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…
A new function algebra of EXPTIME functions by safe nested recursion
Toshiyasu Arai, Naohi Eguchi
Bellantoni and Cook have given a function-algebra characterization of the polynomial-time computable functions via an unbounded recursion scheme which is called safe recursion. Ins…