Unrestricted termination and non-termination arguments for bit-vector programs
Proving program termination is typically done by finding a well-founded ranking function for the program states. Existing termination provers typically find ranking functions using either linear algebra or templates. As such they are often restricted to finding linear ranking functions over mathemat...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Conference item |
| Published: |
Springer
2015
|
| _version_ | 1797068778265116672 |
|---|---|
| author | David, C Kroening, D Lewis, M |
| author2 | Vitek, J |
| author_facet | Vitek, J David, C Kroening, D Lewis, M |
| author_sort | David, C |
| collection | OXFORD |
| description | Proving program termination is typically done by finding a well-founded ranking function for the program states. Existing termination provers typically find ranking functions using either linear algebra or templates. As such they are often restricted to finding linear ranking functions over mathematical integers. This class of functions is insufficient for proving termination of many terminating programs, and furthermore a termination argument for a program operating on mathematical integers does not always lead to a termination argument for the same program operating on fixed-width machine integers. We propose a termination analysis able to generate nonlinear, lexicographic ranking functions and nonlinear recurrence sets that are correct for fixed-width machine arithmetic and floating-point arithmetic. Our technique is based on a reduction from program termination to second-order satisfaction. We provide formulations for termination and non-termination in a fragment of second-order logic with restricted quantification which is decidable over finite domains [1]. The resulting technique is a sound and complete analysis for the termination of finite-state programs with fixed-width integers and IEEE floating-point arithmetic. |
| first_indexed | 2024-03-06T22:15:00Z |
| format | Conference item |
| id | oxford-uuid:53165f56-54a5-437b-a4a9-05a3d0132cde |
| institution | University of Oxford |
| last_indexed | 2024-03-06T22:15:00Z |
| publishDate | 2015 |
| publisher | Springer |
| record_format | dspace |
| spelling | oxford-uuid:53165f56-54a5-437b-a4a9-05a3d0132cde2022-03-26T16:29:30ZUnrestricted termination and non-termination arguments for bit-vector programsConference itemhttp://purl.org/coar/resource_type/c_5794uuid:53165f56-54a5-437b-a4a9-05a3d0132cdeSymplectic Elements at OxfordSpringer2015David, CKroening, DLewis, MVitek, JProving program termination is typically done by finding a well-founded ranking function for the program states. Existing termination provers typically find ranking functions using either linear algebra or templates. As such they are often restricted to finding linear ranking functions over mathematical integers. This class of functions is insufficient for proving termination of many terminating programs, and furthermore a termination argument for a program operating on mathematical integers does not always lead to a termination argument for the same program operating on fixed-width machine integers. We propose a termination analysis able to generate nonlinear, lexicographic ranking functions and nonlinear recurrence sets that are correct for fixed-width machine arithmetic and floating-point arithmetic. Our technique is based on a reduction from program termination to second-order satisfaction. We provide formulations for termination and non-termination in a fragment of second-order logic with restricted quantification which is decidable over finite domains [1]. The resulting technique is a sound and complete analysis for the termination of finite-state programs with fixed-width integers and IEEE floating-point arithmetic. |
| spellingShingle | David, C Kroening, D Lewis, M Unrestricted termination and non-termination arguments for bit-vector programs |
| title | Unrestricted termination and non-termination arguments for bit-vector programs |
| title_full | Unrestricted termination and non-termination arguments for bit-vector programs |
| title_fullStr | Unrestricted termination and non-termination arguments for bit-vector programs |
| title_full_unstemmed | Unrestricted termination and non-termination arguments for bit-vector programs |
| title_short | Unrestricted termination and non-termination arguments for bit-vector programs |
| title_sort | unrestricted termination and non termination arguments for bit vector programs |
| work_keys_str_mv | AT davidc unrestrictedterminationandnonterminationargumentsforbitvectorprograms AT kroeningd unrestrictedterminationandnonterminationargumentsforbitvectorprograms AT lewism unrestrictedterminationandnonterminationargumentsforbitvectorprograms |