[logic-ml] JAIST Logic Seminar Series

[Takako Nemoto]

皆様

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

問い合わせ先：
根元　多佳子
北陸先端科学技術大学院大学　情報科学系
email: t-nemoto at 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}$.