皆様

ベルン大学の Silvia Steila 博士の講演のお知らせです。 どうぞふるってご参加ください。

問い合わせ先： 根元　多佳子 北陸先端科学技術大学院大学　情報科学系 email: t-nemoto@jaist.ac.jp ---------------------------------------------

*JAIST Logic Seminar Series*

Date: Tuesday 28 February, 2017, 15:20-17:00

Place: JAIST, Collaboration room 7 (I-56) (Access: http://www.jaist.ac.jp/english/location/access.html)

Speaker: Silvia Steila (University of Bern, Switzerland)

Title: The strength of the SCT criterion (Joint work with Emanuele Frittaion and Keita Yokoyama).

In 2001 Lee, Jones and Ben-Amram introduced the notion of size-change termination (SCT) for first order functional programs, a sufficient condition for termination. They proved that a program is size-change terminating if and only if it satisfies a certain property which can be statically verified from the recursive definition of the program. We call this equivalence SCT criterion. We undertake the study of size-change analysis in the context of Reverse Mathematics. In particular, we prove that the SCT criterion is equivalent to $\Sigma_2$-induction over RCA$_{0}$.