Document Open Access Logo

Formal Verification of Termination Criteria for First-Order Recursive Functions

Authors Cesar A. Muñoz, Mauricio Ayala-Rincón , Mariano M. Moscato , Aaron M. Dutle, Anthony J. Narkawicz, Ariane A. Almeida, Andréia B. Avelar, Thiago M. Ferreira Ramos

PDF
Thumbnail PDF

File

LIPIcs.ITP.2021.27.pdf
  • Filesize: 0.85 MB
  • 17 pages

Document Identifiers

Author Details

Cesar A. Muñoz
  • NASA Langley Research Center, Hampton, VA, USA
Mauricio Ayala-Rincón
  • Departments of Computer Science and Mathematics, Universidade de Brasília, Brazil
Mariano M. Moscato
  • National Institute of Aerospace, Hampton, VA, USA
Aaron M. Dutle
  • NASA Langley Research Center, Hampton, VA, USA
Anthony J. Narkawicz
  • Hampton, VA, USA
Ariane A. Almeida
  • Department of Computer Science, Universidade de Brasília, Brazil
Andréia B. Avelar
  • Faculdade de Planaltina, Universidade de Brasília, Brazil
Thiago M. Ferreira Ramos
  • Department of Computer Science, Universidade de Brasília, Brazil

Funding

  • Moscato, Mariano M.: corresponding author; research supported by the National Aeronautics and Space Administration under NASA/NIA Cooperative Agreement NNL09AA00A.
  • Narkawicz, Anthony J.: At NASA at time of contribution.

Cite AsGet BibTex

Cesar A. Muñoz, Mauricio Ayala-Rincón, Mariano M. Moscato, Aaron M. Dutle, Anthony J. Narkawicz, Ariane A. Almeida, Andréia B. Avelar, and Thiago M. Ferreira Ramos. Formal Verification of Termination Criteria for First-Order Recursive Functions. In 12th International Conference on Interactive Theorem Proving (ITP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 193, pp. 27:1-27:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ITP.2021.27

Abstract

This paper presents a formalization of several termination criteria for first-order recursive functions. The formalization, which is developed in the Prototype Verification System (PVS), includes the specification and proof of equivalence of semantic termination, Turing termination, size change principle, calling context graphs, and matrix-weighted graphs. These termination criteria are defined on a computational model that consists of a basic functional language called PVS0, which is an embedding of recursive first-order functions. Through this embedding, the native mechanism for checking termination of recursive functions in PVS could be soundly extended with semi-automatic termination criteria such as calling contexts graphs.

Subject Classification

ACM Subject Classification
  • Theory of computation → Models of computation
  • Software and its engineering → Software verification
  • Computing methodologies → Theorem proving algorithms
Keywords
  • Formal Verification
  • Termination
  • Calling Context Graph
  • PVS

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. Andreas Abel. foetus-termination checker for simple functional programs. Programming Lab Report 474, LMU München, 1998. URL: http://www.cse.chalmers.se/~abela/foetus/.
  2. Ariane Alves Almeida and Mauricio Ayala-Rincón. Formalizing the dependency pair criterion for innermost termination. Sci. Comput. Program., 195:102474, 2020. URL: https://doi.org/10.1016/j.scico.2020.102474.
  3. Andréia B. Avelar. Formalização da automação da terminação através de grafos com matrizes de medida. PhD thesis, Universidade de Brasília, Departamento de Matemática, Brasília, Distrito Federal, Brasil, 2015. In Portuguese. Google Scholar
  4. Yves Bertot and Pierre Castéran. Interactive Theorem Proving and Program Development - Coq'Art: The Calculus of Inductive Constructions. Springer-Verlag Berlin Heidelberg, 2004. URL: https://doi.org/10.1007/978-3-662-07964-5.
  5. Robert S. Boyer and J Strother Moore. A Computational Logic. Academic Press, 1979. Google Scholar
  6. Robert W. Floyd. Assigning meanings to programs. Proceedings of Symposium on Applied Mathematics, 19:19-32, 1967. Google Scholar
  7. Matt Kaufmann, Panagiotis Manolios, and J Strother Moore. Computer-Aided Reasoning: An Approach. Kluwer Academic Publishers, 2000. Google Scholar
  8. Alexander Krauss. Certified size-change termination. In Frank Pfenning, editor, Automated Deduction - CADE-21, pages 460-475, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg. Google Scholar
  9. Chin Soon Lee, Neil D. Jones, and Amir M. Ben-Amram. The size-change principle for program termination. In Conference Record of POPL 2001: The 28th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 81-92, 2001. URL: https://doi.org/10.1145/360204.360210.
  10. Panagiotis Manolios and Daron Vroon. Termination analysis with calling context graphs. In Thomas Ball and Robert B. Jones, editors, Computer Aided Verification, pages 401-414, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg. Google Scholar
  11. Sam Owre, John Rushby, and Natarajan Shankar. PVS: A prototype verification system. In Proceedings of CADE 1992, volume 607 of Lecture Notes in Artificial Intelligence, pages 748-752. Springer, 1992. Google Scholar
  12. Thiago Mendonça Ferreira Ramos, César Muñoz, Mauricio Ayala-Rincón, Mariano Moscato, Aaron Dutle, and Anthony Narkawicz. Formalization of the undecidability of the halting problem for a functional language. In Lawrence S. Moss, Ruy de Queiroz, and Maricarmen Martinez, editors, Logic, Language, Information, and Computation, pages 196-209, Berlin, Heidelberg, 2018. Springer Berlin Heidelberg. Google Scholar
  13. Alan Turing. On computable numbers, with an application to the Entscheidungsproblem. Proc. of the London Mathematical Society, 42(1):230-265, 1937. Google Scholar
  14. Alan Turing. Checking a large routine. In Report of a Conference High Speed Automatic Calculating-Machines, pages 67-69. University Mathematical Laboratory, 1949. Google Scholar
  15. Daron Vroon. Automatically Proving the Termination of Functional Programs. PhD thesis, Georgia Institute of Technology, 2007. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact