The strength of SCT soundness

Frittaion, Emanuele; Pelupessy, Florian; Steila, Silvia; Yokoyama, Keita (2018). The strength of SCT soundness. Journal of logic and computation, 28(6), pp. 1217-1242. Oxford University Press 10.1093/logcom/exy003

[img] Text
strengthOfSCTsoundness_steila.pdf - Published Version
Restricted to registered users only
Available under License Publisher holds Copyright.

Download (603kB) | Request a copy

In this paper we continue the study, from Frittaion, Steila and Yokoyama (2017, Theory and Applications of Models of Computation 14th Annual Conference, Bern, Switzerland, April 20–22, 2017), on size-change termination (SCT) in the context of Reverse Mathematics. We analyse the soundness of the SCT method. In particular, we prove that the statement ‘any programme which satisfies the combinatorial condition provided by the SCT criterion is terminating’ is equivalent to WO(ω3) over RCA0.

Item Type:

Journal Article (Original Article)

Division/Institute:

08 Faculty of Science > Institute of Computer Science (INF)

UniBE Contributor:

Steila, Silvia

Subjects:

000 Computer science, knowledge & systems
500 Science > 510 Mathematics

ISSN:

0955-792X

Publisher:

Oxford University Press

Language:

English

Submitter:

Lukas Jaun

Date Deposited:

08 May 2019 11:18

Last Modified:

23 Oct 2019 02:22

Publisher DOI:

10.1093/logcom/exy003

BORIS DOI:

10.7892/boris.125565

URI:

https://boris.unibe.ch/id/eprint/125565

Actions (login required)

Edit item Edit item
Provide Feedback