論文の概要: Complexity Theory of Randomised Testing
- arxiv url: http://arxiv.org/abs/2607.11811v1
- Date: Mon, 13 Jul 2026 17:08:03 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-14 17:47:21.562617
- Title: Complexity Theory of Randomised Testing
- Title（参考訳）: ランダム化試験の複素性理論
- Abstract要約: ソフトウェアテストにおけるランダムジェネレータの最初の複雑性理論の基礎を提示する。
理論的に生成可能な言語は、エネルブル言語と正確に一致することを示す。
これは、決定可能性の境界でのテストに直接的な意味を持つ。
- 参考スコア（独自算出の注目度）: 0.6999740786886536
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Randomised testing is a widely-used approach to software validation, yet its theoretical foundations remain thin. In particular, the fundamental question of what it means for a set of inputs to be \emph{generable} has gone unanswered in both the literature and folklore. We present the first complexity-theoretic foundations for random generators in software testing. We model generators as Turing transducers that consume random bits and produce string-encoded outputs, and show that the theoretically generable languages coincide exactly with the recursively enumerable languages. This has direct implications for testing at the boundaries of decidability, such as compiler testing. For \emph{efficient} generation, we show that the polynomial-time generable languages lie within \textit{NP}, that certain \textit{NP}-complete languages admit efficient generators, and that -- under standard cryptographic assumptions -- there are languages in \textit{P} for which no efficient generator exists: the complexity of efficienct generation and of efficient decision are not the same. We show space-bounded complexity is the natural framework for generators producing \emph{correlated} samples, capturing methodologies such as coverage-guided fuzzing and symbolic execution. Beyond classification, we characterise efficient generability: a language has a polynomial-time generator iff it admits a \emph{certificate scheme} over a verifier -- so witness planting, the folklore technique behind generators to test SAT solvers, is in a sense the only route to efficient generation. On the design of property-based testing libraries, we prove no library can compositionally derive efficient generators from logical predicates involving conjunction or negation, under standard assumptions. However, restricted classes like \textit{NL} (equivalently, linear Datalog predicates) would admit such a compilation.
- Abstract（参考訳）: ランダム化テストは、ソフトウェア検証に広く使われているアプローチだが、その理論的基盤は依然として薄い。
特に、「emph{generable}」となる一連の入力の意味に関する根本的な疑問は、文学と民間伝承の両方において未解決である。
ソフトウェアテストにおけるランダムジェネレータの最初の複雑性理論の基礎を提示する。
我々は、ランダムビットを消費し、文字列符号化された出力を生成するチューリング変換器としてジェネレータをモデル化し、理論上生成可能な言語が帰納的可算言語と正確に一致することを示す。
これは、コンパイラテストのような決定可能性の境界でのテストに直接的な意味を持つ。
emph{efficient} 生成の場合、多項式時間生成可能な言語は \textit{NP} 内に存在し、特定の \textit{NP} 完備な言語は効率的なジェネレータを許容し、(標準的な暗号的仮定の下では)効率的なジェネレータが存在しない \textit{P} には、効率的なジェネレータの複雑さと効率的な決定の複雑さが同じでない言語が存在することを示す。
空間境界の複雑性は,ジェネレータが生成する「emph{correlated}」サンプルの自然な枠組みであることを示す。
つまり、SATソルバをテストするためのジェネレータの背後にある民間伝承技術である証人植林は、ある意味効率的な生成への唯一の道のりである。
プロパティベースのテストライブラリの設計において、標準仮定の下では、協調や否定を含む論理的述語から効率的なジェネレータを合成的に導出できないことが証明されている。
しかし、 \textit{NL} のような制限されたクラス(同様に線形データログ述語)は、そのようなコンパイルを許容する。
関連論文リスト
- Language Identification with Succinct Machine-Independent Traces [10.036312061637764]
限界の同定を可能にする計算トレースを定義する方法を示す。
言語が定義されているアルファベットの大きさに線形なトークンのアルファベットを用いてトレースを定義する方法を示す。
論文 参考訳（メタデータ） (2026-07-14T07:18:07Z) - Is Code Better Than Language for Algorithmic Reasoning [58.86873062890482]
ツール拡張言語モデルでは、中間表現と実行機構の両方を変えるため、自然言語推論とコード実行パイプラインを比較することは困難である。
モデルは、その推論を実行可能なコードとして表現し、言語モデルは、そのコードを文脈でシミュレートして、回答を生成する。
中間介入は自然言語の推論と有意に異なるものではない(+0.15pp)。
論文 参考訳（メタデータ） (2026-06-14T04:17:21Z) - Mitigating Bias in Locally Constrained Decoding via Tractable Proposals [73.78736135699953]
既存の局所的制約付き復号法は、ミオプティックに次のトークンを隠蔽することで制約を強制する。
最近の研究では、シーケンシャルなモンテカルロ法を用いてバイアスを緩和しているが、効果的な提案分布や潜在的な関数を設計することは重要な課題である。
我々は、$p_mathrmlm( cdot mid mathrmconstraint)$からSMCサンプリングのための提案とポテンシャルを構築するための一般的なアプローチを提案する。
論文 参考訳（メタデータ） (2026-06-01T08:58:18Z) - TENSURE: Fuzzing Sparse Tensor Compilers (Registered Report) [9.083996936429465]
我々は,スパースコンパイラのテストに特化して設計された,最初のブラックボックスファジィフレームワークであるTENSUREを紹介する。
合成されたカーネルの100%の意味論的妥当性を保証する制約ベースの新しい生成アルゴリズムを提案する。
TACOとFinchの2つの最先端システムに対する評価では、特にTACOでは、TENSUREがクラッシュや無音の誤コンパイルを露呈している。
論文 参考訳（メタデータ） (2026-03-19T00:13:14Z) - High-Performance Generation of Constrained Inputs [4.837737516460689]
言語ベースのテストは、文脈のない文法定義と意味制約を組み合わせてテスト入力を生成する。
進化的言語に基づく新しい手法を提案し,現状よりも3～4桁の性能向上を図っている。
本稿では,FANDANGO-RSが1分間に401の多様で複雑で有効なテスト入力を生成できるCサブセットのケーススタディにより,これを実証する。
論文 参考訳（メタデータ） (2025-11-08T12:26:55Z) - On the Query Complexity of Verifier-Assisted Language Generation [35.43462431990329]
本研究では,事前学習した言語モデル生成器を用いて制約付き生成を推論するフレームワークを開発する。
検証者へのアクセスは、難解な問題(情報理論上または計算上)を、難解な問題にレンダリングすることができる。
トークンワイド・リジェクション・サンプリングのような単純なアルゴリズムでさえ、検証器へのアクセスによる大きなメリットを享受できることを示す。
論文 参考訳（メタデータ） (2025-02-17T18:46:32Z) - Exploring Facets of Language Generation in the Limit [10.18252143035175]
任意の可算言語コレクションは、その極限において非一様生成の強い特性を持つ生成子を持つことを示す。
我々は,[KM24]の生成アルゴリズムにおける妥当性と幅の緊張関係を,徹底的な生成の定義を導入して定式化する。
また,包括的生成が可能な言語コレクションの正確な特徴付けも提供する。
論文 参考訳（メタデータ） (2024-11-22T22:13:40Z) - Training Neural Networks as Recognizers of Formal Languages [87.06906286950438]
ニューラルネットワークを文字列のバイナリ分類器として直接訓練し評価する。
3つのニューラルアーキテクチャに対して、チョムスキー階層の様々な言語について結果を提供する。
我々の貢献は、将来の研究において、言語認識の主張を理論的に健全に検証するのに役立つだろう。
論文 参考訳（メタデータ） (2024-11-11T16:33:25Z) - Slaves to the Law of Large Numbers: An Asymptotic Equipartition Property for Perplexity in Generative Language Models [0.0]
言語モデルにより生成された大きなテキストの対数的パープレキシティは、トークン分布の平均エントロピーに収束しなければならないことを示す。
これは、言語モデルによって生成される全ての長い合成テキストが属しなければならない典型的な集合'を定義する。
論文 参考訳（メタデータ） (2024-05-22T16:23:40Z) - Lexinvariant Language Models [84.2829117441298]
離散語彙記号から連続ベクトルへの写像であるトークン埋め込みは、任意の言語モデル(LM)の中心にある
我々は、語彙記号に不変であり、したがって実際に固定トークン埋め込みを必要としないテクスチトレキシン変種モデルについて研究する。
十分長い文脈を条件として,レキシン変項LMは標準言語モデルに匹敵する難易度が得られることを示す。
論文 参考訳（メタデータ） (2023-05-24T19:10:46Z) - Locally Typical Sampling [84.62530743899025]
我々は、今日の確率的言語ジェネレータが、一貫性と流動性のあるテキストを生成する際に不足していることを示します。
本稿では,確率モデルから生成する際の,この基準を強制するための簡易かつ効率的な手順を提案する。
論文 参考訳（メタデータ） (2022-02-01T18:58:45Z) - Zero-Shot Cross-lingual Semantic Parsing [56.95036511882921]
7つのテスト言語に対する並列データを持たないゼロショット問題として,言語間セマンティックパーシングについて検討した。
英文論理形式ペアデータのみを用いて解析知識を付加言語に転送するマルチタスクエンコーダデコーダモデルを提案する。
このシステムは、ゼロショット解析を潜時空間アライメント問題としてフレーム化し、事前訓練されたモデルを改善し、最小のクロスリンガル転送ペナルティで論理形式を生成することができる。
論文 参考訳（メタデータ） (2021-04-15T16:08:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。