論文の概要: The ACPATH Metric: Precise Estimation of the Number of Acyclic Paths in C-like Languages
- arxiv url: http://arxiv.org/abs/1610.07914v4
- Date: Sun, 10 Mar 2024 08:15:44 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-17 17:28:01.822189
- Title: The ACPATH Metric: Precise Estimation of the Number of Acyclic Paths in C-like Languages
- Title（参考訳）: ACPATH測定値:C型言語における非循環経路の正確な推定
- Authors: Roberto Bagnara, Abramo Bagnara, Alessandro Benedetti, Patricia M. Hill,
- Abstract要約: ACPATHは、与えられた関数を通して非循環的な実行パスの数を非常によく見積もることができる。
関数本体が後向きのgogoを含まず、ループ外からのループへのジャンプを含まない場合、そのような推定は実際に正確であることを示す。
- 参考スコア（独自算出の注目度）: 41.94295877935867
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: NPATH is a metric introduced by Brian A. Nejmeh in [13] that is aimed at overcoming some important limitations of McCabe's cyclomatic complexity. Despite the fact that the declared NPATH objective is to count the number of acyclic execution paths through a function, the definition given for the C language in [13] fails to do so even for very simple programs. We show that counting the number of acyclic paths in CFG is unfeasible in general. Then we define a new metric for C-like languages, called ACPATH, that allows to quickly compute a very good estimation of the number of acyclic execution paths through the given function. We show that, if the function body does not contain backward gotos and does not contain jumps into a loop from outside the loop, then such estimation is actually exact.
- Abstract（参考訳）: NPATH は、Brian A. Nejmeh が[13]で導入した計量であり、マッケイブのシクロマティック複雑性の重要な制限を克服することを目的としている。
宣言されたNPATHの目的は関数を通して非循環的な実行パスの数を数えることであるにもかかわらず、[13]で与えられたC言語の定義は、非常に単純なプログラムでもそうはならない。
CFGにおける非循環経路の数を数えることは一般に不可能であることを示す。
次に、与えられた関数を通して非巡回実行経路の数を非常によく推定できるACPATHと呼ばれるC型言語のための新しい計量を定義する。
関数本体が後向きのgogoを含まず、ループ外からのループへのジャンプを含まない場合、そのような推定は実際に正確であることを示す。
関連論文リスト
- C Analyzer : A Static Program Analysis Tool for C Programs [0.0]
C Analyzerは、Cプログラムの静的解析のために開発されたツールである。
本研究は,Cプログラムの静的解析に抽象解釈技術を活用することを目的とする。
論文 参考訳（メタデータ） (2024-01-28T11:43:16Z) - Invariant Relations: A Bridge from Programs to Equations [1.3342735568824553]
任意のレベルにネストしたループを持つプログラムを含む,C型プログラムの関数を導出する手法を提案する。
ループの意味を捉えるために、不変関係の概念を用いる。
論文 参考訳（メタデータ） (2023-10-07T04:11:23Z) - A Circuit Complexity Formulation of Algorithmic Information Theory [1.5483078145498086]
インダクティブ推論のソロモノフ理論に着想を得て,回路複雑性に基づく先行モデルを提案する。
回路複雑性によって測定された単純な説明に対する帰納的バイアスがこの問題に適切であると主張する。
論文 参考訳（メタデータ） (2023-06-25T01:30:37Z) - GraphWalks: Efficient Shape Agnostic Geodesic Shortest Path Estimation [93.60478281489243]
3次元曲面上の測地線経路を近似する学習可能なネットワークを提案する。
提案手法は,最短経路の効率的な近似と測地距離推定を提供する。
論文 参考訳（メタデータ） (2022-05-30T16:22:53Z) - Breaking the Linear Iteration Cost Barrier for Some Well-known
Conditional Gradient Methods Using MaxIP Data-structures [49.73889315176884]
条件勾配法(CGM)は現代の機械学習で広く使われている。
ほとんどの取り組みは、全体の実行時間を短縮する手段として、イテレーションの数を減らすことに重点を置いています。
本稿では,多くの基本最適化アルゴリズムに対して,イテレーション毎のコストがパラメータ数にサブ線形である最初のアルゴリズムを示す。
論文 参考訳（メタデータ） (2021-11-30T05:40:14Z) - Searching for More Efficient Dynamic Programs [61.79535031840558]
本稿では,プログラム変換の集合,変換プログラムの効率を評価するための単純な指標,およびこの指標を改善するための探索手順について述べる。
実際に、自動検索は初期プログラムの大幅な改善を見出すことができることを示す。
論文 参考訳（メタデータ） (2021-09-14T20:52:55Z) - Finding the disjointness of stabilizer codes is NP-complete [77.34726150561087]
我々は、$c-不連続性を計算すること、あるいはそれを定数乗算係数の範囲内で近似することの問題はNP完全であることを示す。
CSSコード、$dコード、ハイパーグラフコードなど、さまざまなコードファミリの相違点に関するバウンダリを提供します。
以上の結果から,一般的な量子誤り訂正符号に対するフォールトトレラント論理ゲートの発見は,計算に難題であることが示唆された。
論文 参考訳（メタデータ） (2021-08-10T15:00:20Z) - On the realistic worst case analysis of quantum arithmetic circuits [69.43216268165402]
量子回路の設計における直観は誤解を招く可能性があることを示す。
また,T数を減らすことで,全深度を増大させることができることを示した。
リップルキャリーを用いた加算回路と乗算回路について述べる。
論文 参考訳（メタデータ） (2021-01-12T21:36:16Z) - Learning algorithms from circuit lower bounds [0.0]
構成回路下界の様々な概念から効率的な学習アルゴリズムの既知の構成を再考する。
難しい問題を解こうとする多くのpサイズの回路の誤りを、特定のインタラクティブな方法で効率的に見つけることができれば、pサイズの回路は一様分布を通じてPACを学ぶことができることを証明します。
論文 参考訳（メタデータ） (2020-12-28T04:47:36Z) - Weakly measured while loops: peeking at quantum states [0.0]
whileループは、量子コンピュータ上の各イテレーションで終了条件をテストする。
弱い測定値を用いて時間ループプリミティブを定義し、摂動と反復毎に得られる情報量とのトレードオフを提供する。
任意に高い確率で、ループが実行するイテレーションの数を最悪のケースで見積もることができる十分な条件を提供しています。
論文 参考訳（メタデータ） (2020-09-18T13:33:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。