Publications of Naohi Eguchi

Refereed papers

A New Order-theoretic Characterisation of the Polytime Computable Functions
Martin Avanzini, Naohi Eguchi and Georg Moser
In Proceedings of 10th Asian Symposium on Programming Languages and Systems (APLAS 2012), Lecture Notes in Computer Science 7705, pp 280 - 295, 2012.
A Path Order for Rewrite Systems that Compute Exponential Time Functions
Martin Avanzini, Naohi Eguchi and Georg Moser
In Proceedings of 22nd International Conference on Rewriting Techniques and Applications (RTA 2011), Leibniz International Proceedings in Informatics 10, pp. 123 - 138, 2011.
A Term-rewriting Characterization of PSPACE [final version PDF]
Naohi Eguchi
In Proceedings of 10th Asian Logic Conference, pp 93 - 112, World Scientific, 2010.
A New Function Algebra of EXPTIME Functions by Safe Nested Recursion
Toshiyasu Arai and Naohi Eguchi
ACM Transactions on Computational Logic, Vol. 10 (4), Article No. 24, 19 pages, 2009.
A Lexicographic Path Order with Slow Growing Derivation Bounds
Naohi Eguchi
Mathematical Logic Quarterly, Vol. 55 (2), pp 212 - 224, 2009.

Proving Termination of Unfolding Graph Rewriting for General Safe Recursion
Naohi Eguchi
To appear in proceedings of 8th International Workshop on Computing with Terms and Graphs (TERMGRAPH 2014), pp 18 - 22. Full version: arXiv:1404.6196, 2014.
Predicative Lexicographic Path Orders: Towards a Maximal Model for Primitive Recursive Functions
Naohi Eguchi
In proceedings of 13th International Workshop on Termination (WST2013), pp 41 - 45, 2013.
A Simplified Characterisation of Provably Computable Functions of the System ID₁ of Inductive Definitions (Extended Abstract)
Naohi Eguchi and Andreas Weiermann
In RIMS Kôkyûroku, No. 1832, Proof Theory and Complexity, pp 39 - 58.
A New Path Order that Induces Tight Polynomial Derivation Lengths (Extended Abstract) [final version PDF]
Martin Avanzini, Naohi Eguchi and Georg Moser
Accepted for presentation at 3rd International Workshop on Developments in Implicit Complexity (DICE 2012), 3 pages, 2012.
On a Correspondence between Predicative Recursion and Register Machines
Martin Avanzini, Naohi Eguchi and Georg Moser
In Proceedings of 12th International Workshop on Termination (WST 2012), pp 15 - 19, 2012.
A New Path Order for Exponential Time [PDF]
Martin Avanzini and Naohi Eguchi
In USB proceedings of 11th International Workshop on Termination (WST 2010), 5 pages, 2010.

A New Term Rewriting Characterisation of ETIME functions.
Martin Avanzini and Naohi Eguchi
Technical report, arXiv: 1312.7284, 11 pages, 2013.
Predicative Lexicographic Path Orders: Towards a Maximal Model for Primitive Recursive Functions.
Naohi Eguchi
Technical report, arXiv: 1308.0247, 16 pages, 2013.
Characterising Complexity Classes by Inductive Definitions in Bounded Arithmetic
Naohi Eguchi
Preprint, 20 pages, June 2013. The same version can be found at arXiv: 1306.5559 [math.LO].
A Simplified Characterisation of Provably Computable Functions of the System ID₁ of Inductive Definitions.
Naohi Eguchi and Andreas Weiermann
Technical report, arXiv: 1205.2879, 27 pages, 2012.
A New Order-theoretic Characterisation of the Polytime Computable Functions
Martin Avanzini, Naohi Eguchi and Georg Moser
Technical report, CoRR: 1201.2553, 29 pages, 2012. A short version of this report appeared in the proceedings of 10th Asian Symposium on Programming Languages and Systems (APLAS 2012)

Implicit Characterizations of Complexity Classes of Functions
Naohi Eguchi
Doctoral Dissertation, Graduate School of Engineering, Kobe University, March 2010.