不変推論における複雑性と情報【JST・京大機械翻訳】

Feldman Yotam M. Y.; Immerman Neil; Sagiv Mooly; Shoham Sharon

プレプリント

J-GLOBAL ID：202202202153195893 整理番号：22P0083634

不変推論における複雑性と情報【JST・京大機械翻訳】

Complexity and Information in Invariant Inference

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (4件)： , , ,
資料名：
発行年： 2019年10月27日プレプリントサーバーでの情報更新日： 2020年01月18日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

本論文では,SATベースの不変推論の複雑さ,安全検証に対する顕著なアプローチについて述べた。遷移系と安全特性を与える多項式長の帰納的不変量を与える問題を考察した。IC3/PDRとそのバリアントのようなアルゴリズムを捕捉するのに十分であるHoare-queryモデルと呼ばれるブラックボックスモデルにおけるこの問題の複雑性を解析した。このモデルにおけるアルゴリズムは,Hoare3重項の妥当性を質問することによって,システムの到達可能状態について学習する。一般に,Hoare-queryモデルにおけるアルゴリズムは,クエリの指数数を必要とすることを示した。著者らの下限は情報理論であり,計算的に制限されないアルゴリズムにも適用され,Hoareクエリの多項式数で得られた部分情報からの一般化の選択は,このクラスで効率的な不変推論手順を導くことができることを示す。次に,PDRにおいて行ったように,豊富なHoareクエリを利用することにより,推論はICE学習のようなアプローチよりも指数的に効率的であり,候補の帰納性チェックを利用するだけであることを示した。単一フレームを持つPDRの簡単なバージョンがクエリの多項式数における不変量を推論する遷移システムのクラスを構築することにより,一方,帰納的チェックと反例のみを用いたあらゆるアルゴリズムは,クエリの指数数を必要とする。結果はまた,質問による正確な概念学習の古典的理論との接続と差異を明らかにし,そして,誘導に対する反例からの学習は,ラベル付き例からの古典的正確な学習より難しいことを暗示した。これは,反例誘導合成の収束速度が反例の形態に依存することを示した。【JST・京大機械翻訳】

, , , , , , , , , , ,
, , , , 【Automatic Indexing@JST】

計算理論

, ,

前のページに戻る