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]](https://boris.unibe.ch/style/images/fileicons/text.png) |
Text
strengthOfSCTsoundness_steila.pdf - Published Version Restricted to registered users only Available under License Publisher holds Copyright. Download (603kB) |
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: |
05 Dec 2022 15:25 |
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 |