Advanced automata-based algorithms for program termination checking
Authors:
Open Access
- 11 June 2018
- journal article
- conference paper
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 53 (4) , 135-150
Abstract
In 2014, Heizmann et al. proposed a novel framework for program termination analysis. The analysis starts with a termination proof of a sample path. The path is generalized to a Büchi automaton (BA) whose language (by construction) represents a set of terminating paths. All these paths can be safely removed from the program. The removal of paths is done using automata difference, implemented via BA complementation and intersection. The analysis constructs in this way a set of BAs that jointly "cover" the behavior of the program, thus proving its termination. An implementation of the approach in Ultimate Automizer won the 1st place in the Termination category of SV-COMP 2017. In this paper, we exploit advanced automata-based algorithms and propose several non-trivial improvements of the framework. To alleviate the complementation computation for BAs---one of the most expensive operations in the framework---, we propose a multi-stage generalization construction. We start with generalizations producing subclasses of BAs (such as deterministic BAs) for which efficient complementation algorithms are known, and proceed to more general classes only if necessary. Particularly, we focus on the quite expressive subclass of semideterministic BAs and provide an improved complementation algorithm for this class. Our experimental evaluation shows that the proposed approach significantly improves the power of termination checking within the Ultimate Automizer framework.Keywords
This publication has 27 references indexed in Scilit:
- Linear Ranking for Linear Lasso Programs2013
- The Abstract Domain of Segmented Ranking Functions2013
- Termination Analysis with Algorithmic Learning2012
- Compositional Termination Proofs for Multi-threaded Programs2012
- Proving program terminationCommunications of the ACM, 2011
- Heap Assumptions on DemandLecture Notes in Computer Science, 2007
- Mechanizing and Improving Dependency PairsJournal of Automated Reasoning, 2007
- Antichains: A New Algorithm for Checking Universality of Finite Automata2006
- A Complete Method for the Synthesis of Linear Ranking Functions2004
- Complementing deterministic Büchi automata in polynomial timeJournal of Computer and System Sciences, 1987