メインナビゲーションにスキップ 検索にスキップ メインコンテンツにスキップ

Predicate abstraction and CEGAR for disproving termination of Higher-Order functional programs

  • Takuya Kuwahara
  • , Ryosuke Sato
  • , Hiroshi Unno
  • , Naoki Kobayashi

研究成果: 書籍/レポート タイプへの寄稿 › 会議への寄与

22   !!Link opens in a new tab 被引用数 (Scopus)

抄録

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.

本文言語英語
ホスト出版物のタイトルComputer Aided Verification - 27th International Conference, CAV 2015, Proceedings
編集者Corina S. Păsăreanu, Daniel Kroening
出版社Springer Verlag
ページ287-303
ページ数17
ISBN(印刷版)9783319216676
DOI
出版ステータス出版済み - 2015
外部発表はい
イベント27th International Conference on Computer Aided Verification, CAV 2015 - San Francisco, 米国
継続期間: 7月 18 2015 → 7月 24 2015

出版物シリーズ

名前Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
巻9207
ISSN(印刷版)0302-9743
ISSN(電子版)1611-3349

その他

その他27th International Conference on Computer Aided Verification, CAV 2015
国/地域米国
CitySan Francisco
Period7/18/15 → 7/24/15

!!!All Science Journal Classification (ASJC) codes

  • 理論的コンピュータサイエンス
  • コンピュータサイエンス一般

フィンガープリント

「Predicate abstraction and CEGAR for disproving termination of Higher-Order functional programs」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。

引用スタイル