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: |

**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.

**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.

**Implicit Characterizations of Complexity Classes of Functions.**- Naohi Eguchi.

Doctoral Dissertation, Graduate School of Engineering, Kobe University, 2010.

**A Simplified Characterisation of Provably Computable Functions of the System ID**_{1}.- 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]

**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 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).

**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.

**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.