論文の概要: Efficient Decomposition Identification of Deterministic Finite Automata from Examples

• arxiv url: http://arxiv.org/abs/2509.24347v1
• Date: Mon, 29 Sep 2025 06:50:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-30 22:32:19.794931
• Title: Efficient Decomposition Identification of Deterministic Finite Automata from Examples
• Title（参考訳）: 決定論的有限オートマタの効率的な分解同定
• Authors: Junjie Meng, Jie An, Yong Li, Andrea Turrini, Fanjiang Xu, Naijun Zhan, Miaomiao Zhang,
• Abstract要約: DFA分解識別問題(DFA-DIP)について検討する。 DFA-DIPアプローチは、Augmented Prefix Tree Acceptors(APTA)由来のSATエンコーディングに依存する 私たちの重要なイノベーションの1つは、APTAをラベル付き例から直接派生した3つの価値付きDFAに置き換えています。
• 参考スコア（独自算出の注目度）: 12.847589897236373
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The identification of deterministic finite automata (DFAs) from labeled examples is a cornerstone of automata learning, yet traditional methods focus on learning monolithic DFAs, which often yield a large DFA lacking simplicity and interoperability. Recent work addresses these limitations by exploring DFA decomposition identification problems (DFA-DIPs), which model system behavior as intersections of multiple DFAs, offering modularity for complex tasks. However, existing DFA-DIP approaches depend on SAT encodings derived from Augmented Prefix Tree Acceptors (APTAs), incurring scalability limitations due to their inherent redundancy. In this work, we advance DFA-DIP research through studying two variants: the traditional Pareto-optimal DIP and the novel states-optimal DIP, which prioritizes a minimal number of states. We propose a novel framework that bridges DFA decomposition with recent advancements in automata representation. One of our key innovations replaces APTA with 3-valued DFA (3DFA) derived directly from labeled examples. This compact representation eliminates redundancies of APTA, thus drastically reducing variables in the improved SAT encoding. Experimental results demonstrate that our 3DFA-based approach achieves significant efficiency gains for the Pareto-optimal DIP while enabling a scalable solution for the states-optimal DIP.
• Abstract（参考訳）: ラベル付き例から決定論的有限オートマトン(DFA)を識別することはオートマトン学習の基盤であるが、従来の手法はモノリシックなDFAを学習することに重点を置いており、多くの場合、単純さと相互運用性に欠ける大きなDFAを生み出す。 最近の研究は、DFA分解識別問題(DFA-DIP)を探索し、複数のDFAの交点としてシステム挙動をモデル化し、複雑なタスクに対してモジュラリティを提供する。 しかし、既存のDFA-DIPアプローチは、Augmented Prefix Tree Acceptors (APTA) から派生したSATエンコーディングに依存しており、固有の冗長性のためにスケーラビリティの制限が生じる。 本研究では、従来のパレート最適DIPと、最小限の状態を優先する新しい状態最適DIPの2つの変種を研究することによって、DFA-DIP研究を進める。 自動表現の最近の進歩とともにDFA分解を橋渡しする新しいフレームワークを提案する。 私たちの重要なイノベーションのひとつが,ラベル付き例から直接派生した,APTAを3値のDFA(3DFA)に置き換えています。 このコンパクト表現はAPTAの冗長性を排除し、改良されたSAT符号化における変数を大幅に削減する。 実験の結果、3DFAに基づくアプローチはパレート最適DIPに対して大きな効率向上を実現し、かつ状態最適化DIPのスケーラブルな解を可能にした。

関連論文リスト

• Light-IF: Endowing LLMs with Generalizable Reasoning via Preview and Self-Checking for Complex Instruction Following [10.119219532863767]
  思考段階の怠慢な推論は 指示の順守に 寄与する主要な要因だ 本稿では,プレビューと自己チェックを含む厳密な推論プロセスを実現するための包括的フレームワークを提案する。 私たちのLight-IF-32Bモデルは、DeepSeek-R1のような大規模なオープンソースモデルと、Doubao-1.6のようなクローズドソースモデルの両方を上回っています。
  論文  参考訳（メタデータ） (2025-08-05T07:42:00Z)
• TRIDENT: Temporally Restricted Inference via DFA-Enhanced Neural Traversal [11.042648980854485]
  TRIDENTは、再トレーニングを必要とせず、時間的制約の遵守を保証する推論時アルゴリズムである。 TRIDENTは完全な制約満足度を実現し,最先端技術と比較すると,効率と高品質の指標が向上している。
  論文  参考訳（メタデータ） (2025-06-11T13:14:01Z)
• Joint Transmit and Pinching Beamforming for Pinching Antenna Systems (PASS): Optimization-Based or Learning-Based? [89.05848771674773]
  MISO (Multiple-input Single-output) フレームワークを提案する。 それは複数の導波路で構成されており、多数の低コストアンテナ(PA)を備えている。 PAの位置は、大規模パスと空間の両方にまたがるように再構成することができる。
  論文  参考訳（メタデータ） (2025-02-12T18:54:10Z)
• PIPA: Preference Alignment as Prior-Informed Statistical Estimation [57.24096291517857]
  本稿では、RLフリーな統一確率的フレームワークであるPIPA(Pior-Informed Preference Alignment)を紹介する。 PIPAはペアデータとアンペアデータの両方に対応し、回答とステップレベルのアノテーションを提供する。 異なる種類の事前情報を統合することにより,PIPA-MとPIPA-Nの2種類のPIPAを開発した。
  論文  参考訳（メタデータ） (2025-02-09T04:31:30Z)
• Understanding the Logic of Direct Preference Alignment through Logic [54.272600416107146]
  本稿では,単一モデルと参照モデルに基づくアプローチの選好損失を特徴付ける新しいフォーマリズムを提案する。 そこで我々は,この嗜好学習の形式的視点が,DPA損失景観の大きさと構造の両方に新たな光を当てていることを示す。
  論文  参考訳（メタデータ） (2024-12-23T16:23:13Z)
• DFAMiner: Mining minimal separating DFAs from labelled samples [8.196522686887713]
  DFAMinerは、ラベル付きサンプルから最小限の決定論的有限オートマトン(DFA)を分離するパッシブ学習ツールである。 まず,ラベル付きサンプルの集合から3値のDFAを漸進的に構築する,単純で線形時間アルゴリズムを提案する。 そこで我々は,SAT問題を最小化して構築したオートマトンを最小化することにより,ラベル付きサンプルの最小分離DFAをマイニングするツールを開発した。
  論文  参考訳（メタデータ） (2024-05-29T08:31:34Z)
• Regularizing Variational Autoencoder with Diversity and Uncertainty Awareness [61.827054365139645]
  変分オートエンコーダ(VAE)は、償却変分推論に基づいて潜伏変数の後部を近似する。 よりディバースで不確実な潜在空間を学習するための代替モデルDU-VAEを提案する。
  論文  参考訳（メタデータ） (2021-10-24T07:58:13Z)

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

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