12 citations · 17 across the 11 of their papers we have counts for
Showing 2013Show all
3 papers · 1 filter
cs.LO2013
A New Term Rewriting Characterisation of ETIME functions
Martin Avanzini, Naohi Eguchi
Adopting former term rewriting characterisations of polytime and exponential-time computable functions, we introduce a new reduction order, the Path Order for ETIME (POE* for short…
math.LO2013
Predicative Lexicographic Path Orders: An Application of Term Rewriting to the Region of Primitive Recursive Functions
Naohi Eguchi
In this paper we present a novel termination order the {\em predicative lexicographic path order} (PLPO for short), a syntactic restriction of the lexicographic path order. As well…
math.LO2013★ 2 cited
Characterising Complexity Classes by Inductive Definitions in Bounded Arithmetic
Naohi Eguchi
Famous descriptive characterisations of P and PSPACE are restated in terms of the Cook-Nguyen style second order bounded arithmetic. We introduce an axiom of inductive definitions…