English Japanese
Home   Research Activities   Publications


Refereed papers

Extended abstracts

Preprint, Technical reports

Thesis


 

Publications of Naohi Eguchi

Refereed papers

Formalizing Termination Proofs under Polynomial Quasi-interpretations
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 Order-theoretic 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 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 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 Term-rewriting 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 Quasi-interpretations
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 ID1 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 ID1 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, 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
Back to Page Top