TY - GEN
T1 - Predicate abstraction and CEGAR for disproving termination of Higher-Order functional programs
AU - Kuwahara, Takuya
AU - Sato, Ryosuke
AU - Unno, Hiroshi
AU - Kobayashi, Naoki
N1 - Publisher Copyright:
© Springer International Publishing Switzerland 2015.
PY - 2015
Y1 - 2015
N2 - We propose an automated method for disproving termination of higher-order functional programs. Our method combines higherorder model checking with predicate abstraction and CEGAR. Our predicate abstraction is novel in that it computes a mixture of under- and overapproximations. For non-determinism of a source program (such as random number generation), we apply underapproximation to generate a subset of the actual branches, and check that some of the branches in the abstract program is non-terminating. For operations on infinite data domains (such as integers), we apply overapproximation to generate a superset of the actual branches, and check that every branch is nonterminating. Thus, disproving non-termination reduces to the problem of checking a certain branching property of the abstract program, which can be solved by higher-order model checking. We have implemented a prototype non-termination prover based on our method and have confirmed the effectiveness of the proposed approach through experiments.
AB - We propose an automated method for disproving termination of higher-order functional programs. Our method combines higherorder model checking with predicate abstraction and CEGAR. Our predicate abstraction is novel in that it computes a mixture of under- and overapproximations. For non-determinism of a source program (such as random number generation), we apply underapproximation to generate a subset of the actual branches, and check that some of the branches in the abstract program is non-terminating. For operations on infinite data domains (such as integers), we apply overapproximation to generate a superset of the actual branches, and check that every branch is nonterminating. Thus, disproving non-termination reduces to the problem of checking a certain branching property of the abstract program, which can be solved by higher-order model checking. We have implemented a prototype non-termination prover based on our method and have confirmed the effectiveness of the proposed approach through experiments.
UR - https://www.scopus.com/pages/publications/84950986285
UR - https://www.scopus.com/pages/publications/84950986285#tab=citedBy
U2 - 10.1007/978-3-319-21668-3_17
DO - 10.1007/978-3-319-21668-3_17
M3 - Conference contribution
AN - SCOPUS:84950986285
SN - 9783319216676
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 287
EP - 303
BT - Computer Aided Verification - 27th International Conference, CAV 2015, Proceedings
A2 - Păsăreanu, Corina S.
A2 - Kroening, Daniel
PB - Springer Verlag
T2 - 27th International Conference on Computer Aided Verification, CAV 2015
Y2 - 18 July 2015 through 24 July 2015
ER -