論文の概要: Testing and Learning Symbolic Finite State Machines
- arxiv url: http://arxiv.org/abs/2609.25603v1
- Date: Tue, 22 Sep 2026 02:51:23 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-23 18:04:04.186768
- Title: Testing and Learning Symbolic Finite State Machines
- Title（参考訳）: 記号型有限状態マシンのテストと学習
- Abstract要約: 記号有限状態機械(SFSM)はガードと出力の割り当てを使って入力/出力の振る舞いを記述している。
我々は、関連するガードオーバーラップの証人を含む有限代表入力セットを定義し、それらのオーバーラップが異なる出力割り当ての証人を切り離す。
我々の主定理は、有限インスタンス化の言語同値性は全入力領域上の言語同値性を意味することを示している。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Symbolic finite state machines (SFSMs) describe input/output behaviour using guards and output assignments with possibly infinite data domains. We study deterministic and completely specified SFSMs whose guards and output assignments depend only on the current input. We define finite representative input sets that contain witnesses for relevant guard overlaps and separating witnesses for output assignments that differ on those overlaps. Our main theorem shows that language equivalence of the finite instantiations implies language equivalence over the full input domain. This result transfers complete testing methods for deterministic finite state machines (DFSMs) to SFSMs, provided finite sets of admissible guards and output assignments and an upper bound on the number of distinguishable reachable states are known. Under these assumptions, a DFSM learner with complete testing can learn a finite instantiation, which is then lifted to an equivalent SFSM. We establish a bound on the size of representative input sets and give an SMT construction whose correctness and termination hold under stated solver assumptions.
- Abstract（参考訳）: 記号有限状態機械(SFSM)はガードと出力の割り当てを使って入力/出力の振る舞いを記述している。
本研究では、現在の入力のみに依存するガードと出力の割り当てを持つ決定論的かつ完全に特定されたSFSMについて検討する。
我々は、関連するガードオーバーラップの証人を含む有限代表入力セットを定義し、それらのオーバーラップが異なる出力割り当ての証人を切り離す。
我々の主定理は、有限インスタンス化の言語同値性は全入力領域上の言語同値性を意味することを示している。
この結果は、決定論的有限状態機械(DFSM)の完全なテスト手法をSFSMに転送し、許容されるガードと出力の割り当ての有限セットと、識別可能な到達可能な状態の数に対する上限が知られている。
これらの仮定の下で、DFSM学習者は有限インスタンス化を学習し、それを等価SFSMに持ち上げることができる。
我々は、代表入力集合のサイズに縛りを定め、その正しさと終端が従うSMT構成を与える。
関連論文リスト
- Codified Finite-state Machines for Role-playing [70.86310301713068]
テキスト文字プロファイルをFSMに自動的に符号化するフレームワークであるCFSM(Codified Finite-State Machines)を紹介する。
CFSMはプロファイルから直接キー状態と遷移を抽出し、文字の一貫性を強制する解釈可能な構造を生成する。
我々はCFSMをCPFSM(Codified Probabilistic Finite-State Machines)に拡張し、遷移を状態上の確率分布としてモデル化する。
論文 参考訳（メタデータ） (2026-02-05T17:19:18Z) - AlignSAE: Concept-Aligned Sparse Autoencoders [47.18866175760984]
本稿では,SAE の機能と定義オントロジーを"pre-train, then-train" カリキュラムで整合させる手法である AlignSAE を紹介する。
初期教師なしトレーニングフェーズの後、特定の概念を専用潜在スロットにバインドするために教師付きポストトレーニングを適用する。
この分離により、非関係な特徴から干渉することなく、特定の関係を検査・制御できる解釈可能なインターフェースが生成される。
論文 参考訳（メタデータ） (2025-12-01T18:58:22Z) - On the Statistical Query Complexity of Learning Semiautomata: a Random Walk Approach [59.589793281734636]
我々は,アルファベットサイズと入力長の両方が状態数である場合に,統計的クエリの硬さを確立することができることを示す。
この結果は、半オートマタの内部状態遷移構造からのみ導かれる。
論文 参考訳（メタデータ） (2025-10-05T09:35:35Z) - On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoning [87.73401758641089]
CoT推論による現代言語モデル(LM)の性能向上
LMは弦上の分布の族を確率的チューリングマシンと同一に表現できることを示す。
論文 参考訳（メタデータ） (2024-06-20T10:59:02Z) - Bisimulation Learning [55.859538562698496]
我々は、大きな、潜在的に無限の状態空間を持つ状態遷移系の有限バイシミュレートを計算する。
提案手法は,実際に行われている他の最先端ツールよりも高速な検証結果が得られる。
論文 参考訳（メタデータ） (2024-05-24T17:11:27Z) - Grammar-Constrained Decoding for Structured NLP Tasks without Finetuning [27.59524153097858]
文法制約付き復号法(GCD)は、大言語モデル(LM)の生成を制御するために用いられる。
GCDは一般に構造化NLPタスクの統一フレームワークとして機能する。
文法制約付きLMは、制約なしLMよりも大幅に優れるか、タスク固有の微調整モデルよりも優れていることを示す。
論文 参考訳（メタデータ） (2023-05-23T11:54:37Z) - SMT-based Safety Verification of Parameterised Multi-Agent Systems [78.04236259129524]
パラメータ化マルチエージェントシステム(MAS)の検証について検討する。
特に、与えられた状態公式として特徴づけられる不要な状態が、所定のMASで到達可能かどうかについて検討する。
論文 参考訳（メタデータ） (2020-08-11T15:24:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。