論文の概要: New Fault Domains for Conformance Testing of Finite State Machines

• arxiv url: http://arxiv.org/abs/2410.19405v2
• Date: Wed, 11 Jun 2025 20:09:48 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-13 15:37:22.069653
• Title: New Fault Domains for Conformance Testing of Finite State Machines
• Title（参考訳）: 有限状態機械の整合性試験のための新しい断層領域
• Authors: Frits Vaandrager, Ivo Melse,
• Abstract要約: 障害ドメインは、テスト中に検出する必要がある障害に関するテスターの仮定を反映します。 2つの有名な$m$-completeテストスイート生成戦略に対して、$k$-$A$-completenessの条件を示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A fault domain reflects a tester's assumptions about faults that may occur in an implementation and that need to be detected during testing. A fault domain that has been widely studied in the literature on black-box conformance testing is the class of finite state machines (FSMs) with at most $m$ states. Numerous strategies for generating test suites have been proposed that guarantee fault coverage for this class. These so-called $m$-complete test suites grow exponentially in $m-n$, where $n$ is the number of states of the specification, so one can only run them for small values of $m-n$. But the assumption that $m-n$ is small is not realistic in practice. In his seminal paper from 1964, Hennie raised the challenge to design checking experiments in which the number of states may increase appreciably. In order to solve this long-standing open problem, we propose (much larger) fault domains that capture the assumption that all states in an implementation can be reached by first performing a sequence from some set $A$ (typically a state cover for the specification), followed by $k$ arbitrary inputs, for some small $k$. The number of states of FSMs in these fault domains grows exponentially in $k$. We present a sufficient condition for $k$-$A$-completeness of test suites with respect to these fault domains. Our condition implies $k$-$A$-completeness of two prominent $m$-complete test suite generation strategies, the Wp and HSI methods. Thus these strategies are complete for much larger fault domains than those for which they were originally designed, and thereby solve Hennie's challenge. We show that three other prominent $m$-complete methods (H, SPY and SPYH) do not always generate $k$-$A$-complete test suites.
• Abstract（参考訳）: 障害ドメインは、実装で発生し、テスト中に検出する必要がある障害に関するテスターの仮定を反映します。 ブラックボックス適合性試験に関する文献で広く研究されている断層領域は、有限状態機械(FSM)のクラスであり、少なくとも$m$状態を持つ。 このクラスの障害カバレッジを保証するために、テストスイートを生成するための多くの戦略が提案されている。 いわゆる$m$-completeテストスイートは、$m-n$で指数関数的に増加する。 しかし、$m-n$が小さいという仮定は現実的には現実的ではない。 1964年の論文の中で、ハニーは国家の数が順調に増加する可能性のある検査実験を設計する挑戦を提起した。 この長年続くオープンな問題を解決するために、我々は、あるセット$A$(通常仕様のステートカバー)のシーケンスを実行し、次に$k$の任意の入力を実行して、実装中のすべての状態に到達できるという仮定を捉える(非常に大きい)フォールトドメインを提案する。 これらの断層領域におけるFSMの状態の数は、指数関数的に$k$で増加する。 これらの障害ドメインに関して、テストスイートの$k$-$A$完全性について十分な条件を示す。 我々の条件は、$k$-$A$-completeness of two prominent $m$-complete test suite generation strategy, the Wp and HSI methodである。 したがって、これらの戦略はもともと設計されていたものよりもはるかに大きな障害領域に対して完全であり、したがってヘニーの課題を解決している。 他の3つの注目すべき$m$-completeメソッド(H、SPY、SPYH)は、必ずしも$k$-$A$-completeテストスイートを生成するわけではない。

関連論文リスト

• Nearly tight bounds for testing tree tensor network states [0.0]
  ツリーテンソルネットワーク状態(TTNS)は、シュミットランクが低いから多部量子状態を持つという概念を一般化する。 我々は、未知の純状態が、結合次元が最大$r$の$n$クォーディット上のTTNSであるかどうかをテストするタスクを研究する。 また,少数のコピーに対して一度に実施した測定値を用いて,テストの性能についても検討した。
  論文  参考訳（メタデータ） (2024-10-28T18:13:38Z)
• Testing the Feasibility of Linear Programs with Bandit Feedback [53.40256244941895]
  我々は,低回帰アルゴリズムと反復対数の漸近法則に基づくテストを開発する。 このテストが信頼できることを証明し、信号レベルに適応する'$Gamma,$ of any instance。 信頼性テストのサンプルコストに対して、最小限の$(Omegad/Gamma2)$で補う。
  論文  参考訳（メタデータ） (2024-06-21T20:56:35Z)
• Permutation tests for quantum state identity [0.0]
  n$未知の量子状態が等しいか不等であるかを決定する問題は、量子状態アイデンティティ問題として知られている。 置換テストはこのタスクに最適であることが知られており、2つの入力状態に対してはよく知られたスワップテストと一致する。 この研究は、量子状態のアイデンティティ問題(きめ細かい定式化)の基盤となる構造を捉えようとする。
  論文  参考訳（メタデータ） (2024-05-15T18:00:07Z)
• Collaborative non-parametric two-sample testing [55.98760097296213]
  目標は、null仮説の$p_v = q_v$が拒否されるノードを特定することである。 グラフ構造を効率的に活用する非パラメトリックコラボレーティブ2サンプルテスト(CTST)フレームワークを提案する。 提案手法は,f-divergence Estimation, Kernel Methods, Multitask Learningなどの要素を統合する。
  論文  参考訳（メタデータ） (2024-02-08T14:43:56Z)
• Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Path [106.37656068276902]
  本稿では,最短経路(SSP)問題において,$epsilon$-optimal Policyを学習する際のサンプル複雑性について検討する。 学習者が生成モデルにアクセスできる場合、複雑性境界を導出する。 我々は、$S$状態、$A$アクション、最小コスト$c_min$、およびすべての状態に対する最適ポリシーの最大期待コストを持つ最悪のSSPインスタンスが存在することを示す。
  論文  参考訳（メタデータ） (2022-10-10T18:34:32Z)
• Prioritized Variable-length Test Cases Generation for Finite State Machines [0.09786690381850353]
  モデルベーステスト(MBT)は、システムアンダーテストの一部が有限状態マシン(FSM)の特性を持つ場合のテストに有効な手法である。 本稿では,これらの要件をすべて満たしたテスト生成戦略を提案する。 本論文では,FSMの適用状況に応じて,機能的および非機能的ソフトウェア要件のテストにも適用可能である。
  論文  参考訳（メタデータ） (2022-03-17T20:16:45Z)
• Testing matrix product states [5.225550006603552]
  未知の状態$|psirangle$が特性試験モデルにおける行列積状態(MPS)かどうかをテストする。 MPS(英: MPS)は、量子多体系の研究で生じる物理関連量子状態のクラスである。
  論文  参考訳（メタデータ） (2022-01-05T21:10:50Z)
• Improved Sample Complexity for Incremental Autonomous Exploration in MDPs [132.88757893161699]
  我々は $epsilon$-optimal 目標条件付きポリシーのセットを学び、$ L$ ステップ内で段階的に到達可能なすべての状態を達成します。 DisCoは、コストに敏感な最短経路問題に対して$epsilon/c_min$-optimalポリシーを返すことができる最初のアルゴリズムです。
  論文  参考訳（メタデータ） (2020-12-29T14:06:09Z)
• Optimal Testing of Discrete Distributions with High Probability [49.19942805582874]
  高確率状態に着目して離散分布を試験する問題について検討する。 一定の要素でサンプル最適である近接性および独立性テストのための最初のアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2020-09-14T16:09:17Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。