Refereed papers
Extended abstracts
Preprint, Technical reports
Thesis


Publications of Naohi Eguchi
Refereed papers
 Formalizing Termination Proofs under Polynomial Quasiinterpretations
 Naohi Eguchi
In Proceedings of 10th International Workshop on Fixed Points in Computer Science, Electronic Proceedings in Theoretical Computer Science Vol. 191, pp 33 – 47, 2015
 Complexity Analysis of Precedence Terminating Infinite Graph Rewrite Systems
 Naohi Eguchi
8th International Workshop on Computing with Terms and Graphs (TERMGRAPH 2014), Revised Selected Papers, Electronic Proceedings in Theoretical Computer Science Vol. 183, pp 33  47, 2015
 A New Ordertheoretic Characterisation of the Polytime Computable Functions
 Martin Avanzini, Naohi Eguchi and Georg Moser
Theoretical Computer Science Vol. 585, pp 3  24, 2015
 Predicative Lexicographic Path Orders  An Application of Term Rewriting to the Region of Primitive Recursive Functions
 Naohi Eguchi
3rd International Conference on Foundational and Practical Aspects of Resource Analysis (FOPARA 2013), Revised Selected Papers, Lecture Notes in Computer Science Vol. 8552, pp 77  92, 2014
Final version with minor corrections (arXiv: 1308.0247)
 A New Ordertheoretic 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 Vol. 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 Vol. 10, pp. 123  138, 2011
 A Termrewriting Characterization of PSPACE
 Naohi Eguchi
10th Asian Logic Conference (ALC 2008), Revised Selected Papers, World Scientific, pp 93  112, 2010 [final version PDF]
 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
Extended abstracts
 Formalizing Termination Proofs under Polynomial Quasiinterpretations
 Naohi Eguchi
Accepted for 16th International Workshop on Logic and Computational Complexity (LCC 2015), 4 pages, 2015
 Proving Termination of Unfolding Graph Rewriting for General Safe Recursion
 Naohi Eguchi
In Proceedings of 8th International Workshop on Computing with Terms and Graphs (TERMGRAPH 2014), pp 18  22, 2014.
Full version (arXiv: 1404.6196)
 A New Term Rewriting Characterisation of ETIME functions
 Martin Avanzini and Naohi Eguchi
Accepted for 5th International Workshop on Developments in Implicit Complexity (DICE 2014), 5 pages, 2014
 Predicative Lexicographic Path Orders: Towards a Maximal Model for Primitive Recursive Functions
 Naohi Eguchi
In Proceedings of 13th International Workshop on Termination (WST 2013), pp 41  45, 2013
 A Simplified Characterisation of Provably Computable Functions of the System ID_{1} of Inductive Definitions (Extended Abstract)
 Naohi Eguchi and Andreas Weiermann
In RIMS Kôkyûroku, No. 1832, Proof Theory and Complexity, pp 39  58, 2013
 A New Path Order that Induces Tight Polynomial Derivation Lengths (Extended Abstract)
 Martin Avanzini, Naohi Eguchi and Georg Moser
Accepted for 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
 Martin Avanzini and Naohi Eguchi
In Proceedings of 11th International Workshop on Termination (WST 2010), 5 pages, 2010
Preprints, Technical Reports
 A New Term Rewriting Characterisation of ETIME functions
 Martin Avanzini and Naohi Eguchi
Technical report, arXiv: 1312.7284, 10 pages, 2013
 Characterising Complexity Classes by Inductive Definitions in Bounded Arithmetic
 Naohi Eguchi
Technical report, arXiv: 1306.5559, 20 pages, 2013
 A Simplified Characterisation of Provably Computable Functions of the System ID_{1} of Inductive Definitions
 Naohi Eguchi and Andreas Weiermann
Technical report, arXiv: 1205.2879, 27 pages, 2012
 A New Ordertheoretic Characterisation of the Polytime Computable Functions
 Martin Avanzini, Naohi Eguchi and Georg Moser
Technical report, arXiv: 1201.2553, 29 pages, 2012
Thesis
 Implicit Characterizations of Complexity Classes of Functions
 Naohi Eguchi
Doctoral Dissertation, Graduate School of Engineering, Kobe University, 2010
