English Japanese
Publications   Selected Talks   Organisational Works   Joint Research Project

Home Page of Naohi Eguchi (till March 2013)

Dr., Postdoctoral Fellow

Thanks to John Templeton Foundation I started working at Mathematical Institute, Tohoku University in August 2011 (Grant title: Philosophical frontiers in Reverse Mathematics. Project Leaders: Sam Sanders and Keita Yokoyama). Currently I am a member of Logic Group of Prof. Kazuyuki Tanaka.

Research Interests: Implicit computational complexity, Complexity analysis by term rewriting, Bounded arithmetic, Ordinal analysis, Reverse mathematics.
Profile: Naohi Eguchi (Read & Researchmap)
Address: Mathematical Institute, Tohoku University 6-3, Aramaki Aza-Aoba, Aoba-ku, Sendai, Miyagi 980-8578, Japan
Tel: +81-22-795-3889
E-mail:

What's new!

Mar. 27, 2013. Page of Joint Research Project - Ghent University/Tohoku University was made.
Aug. 31, 2012. Publications were updated.
Jan. 4, 2012. The homepage was renewed!
Last update: March 27, 2013.

Publications

Refereed papers

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.
Naohi Eguchi.
In Proceedings of 10th Asian Logic Conference, pp 93 - 112, World Scientific, 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.

Thesis

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

Abstracts

A Simplified Characterisation of Provably Computable Functions of the System ID1.
Naohi Eguchi and Andreas Weiermann.
TURING CENTENARY CONFERENCE CiE 2012 - How the World Computes, 1 page. [PDF]
A New Path Order that Induces Tight Polynomial Derivation Lengths (Extended Abstract).
Martin Avanzini, Naohi Eguchi and Georg Moser.
Extended Abstract accepted to 3rd International Workshop on Developments in Implicit Complexity (DICE 2012), 3 pages. [PDF]
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. [PDF]

Technical Reports

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, CoRR: 1201.2553, 29 pages, 2012. A polished version of this report has been accepted to the proceedings of 10th Asian Symposium on Programming Languages and Systems (APLAS 2012).
Page Top

Selected Talks

Weak Theories of Arithmetic for Computational Complexity: A Gentle Introduction.
Sendai Logic Seminar, May 2012, Tohoku University, Japan.
Order-theoretic Approaches to Computational Complexity - Towards more natural characterisations.
Workshop on Proof Theory and Computability Theory 2012 - Philosophical Frontiers in Reverse Mathematics, February 2012, Harumi Grand Hotel, Tokyo, Japan. [slide]
Term-rewriting Approaches to Implicit Computational Complexity.
Workshop on Linear Logic - Geometry of Interaction Traced Monoidal Categories and Implicit Complexity, November 2011, Kyoto University, Japan. [slide]
On Classifying the Provably Total Functions of the Theory of Non-iterated Inductive Definitions.
(joint work with Andreas Weiermann) Sendai Logic Seminar, July 2011, Tohoku University, Japan. [slide]
Implicit Characterisations of Complexity Classes by Rewriting.
May 2011, Ghent University, Belgium. [slide]
Towards a Theory of Bounded Arithmetic for Polynomial Space Functions.
(joint work with Toshiyasu Arai) Sendai Logic Seminar, December 2010, Tohoku University, Japan. [slide]
Complexity Analysis by Rewriting for Exponential Time.
(joint work with Martin Avanzini and Georg Moser) 6th Theorem Proving and Provers Meeting (TPP 2010), November 2010, Nagoya University, Japan. [slide]
A Rewriting Characterization of the Polynomial Space Functions.
3rd Austria-Japan Summer Workshop on Term Rewriting (AJSW 2010), August 2010, Obergurgl University Centre, Austria.
On Provably Total Number-theoretic Functions of Fragments of Set Theories.
Mita Logic Seminar - A Proof Theory Workshop with Lecture Series by Grigori Mints, March 2010, Keio University, Japan.
Page Top

Organisational Works

Workshop on Proof Theory and Computability Theory 2012 - Philosophical Frontiers in Reverse Mathematics.
February 20 - 23, 2012. Harumi Grand Hotel, Tokyo, Japan.
Organising committee: Kazuyuki Tanaka (chair), Andreas Weiermann (chair), Toshiyasu Arai, Naohi Eguchi, Hajime Ishihara, Sam Sanders and Takeshi Yamazaki.
Workshop on Proof Theory and Computability Theory.
February 2011, Akiu Spa Hotel Iwanumaya, Sendai, Miyagi, Japan.
Organisers: Hajime Ishihara (JAIST) and Kazuyuki Tanaka (Tohoku University).
Local organisers: Takeshi Yamazaki, Sam Sanders, Keita Yokoyama and Naohi Eguchi.
Page Top