論文の概要: Logic-Gated Time-Shared Feedforward Networks for Alternating Finite Automata: Exact Simulation and Learnability
- arxiv url: http://arxiv.org/abs/2604.01228v1
- Date: Fri, 20 Mar 2026 06:14:49 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-04-06 02:36:13.220216
- Title: Logic-Gated Time-Shared Feedforward Networks for Alternating Finite Automata: Exact Simulation and Learnability
- Title（参考訳）: 交代有限オートマタのための論理ゲート型時間共有フィードフォワードネットワーク:厳密なシミュレーションと学習性
- Authors: Sahil Rajesh Dhayalkar,
- Abstract要約: 論理ゲート型時間共有フィードフォワードネットワーク(LG-TS-FFN)を用いた有限オートマタ(AFAs)のシミュレーションフレームワークを提案する。
我々のアーキテクチャは、異なる論理ゲートとして機能する学習可能な状態依存バイアスを統合し、既存のtextsctextscORとUniversal textsctextscANDアグリゲーションの両方の表現を可能にします。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We present a formal and constructive framework for simulating Alternating Finite Automata (AFAs) using Logic-Gated Time-Shared Feedforward Networks (LG-TS-FFNs). Unlike prior neural automata models limited to Nondeterministic Finite Automata (NFAs) and existential reachability, our architecture integrates learnable, state-dependent biases that function as differentiable logic gates, enabling the representation of both Existential \textsc{\textsc{OR}} and Universal \textsc{\textsc{AND}} aggregation within a shared-parameter linear recurrence. We prove that this architectural modification upgrades the network's computational class to be structurally isomorphic to AFAs, thereby inheriting their exponential succinctness: the network can represent regular languages requiring $2^n$ states in an NFA with only $n$ neurons. We rigorously establish that the forward pass of an LG-TS-FFN exactly simulates the reachability dynamics of an AFA, including instantaneous $\varepsilon$-closures. Furthermore, we demonstrate empirical learnability: a continuous relaxation of the logic gates allows the network to simultaneously recover the automaton's topology and logical semantics from binary labels via standard gradient descent. Extensive experiments confirm that our model achieves perfect recovery of ground-truth automata, bridging the gap between statistical learning and succinct, universal logical reasoning.
- Abstract（参考訳）: 本稿では、論理ゲート型時間共有フィードフォワードネットワーク(LG-TS-FFN)を用いて、有限オートマタ(AFAs)をシミュレートするための形式的で建設的なフレームワークを提案する。
非決定論的有限オートマタ(NFA)や存在到達性に制限された以前の神経オートマトンモデルとは異なり、我々のアーキテクチャは、微分可能な論理ゲートとして機能する学習可能な状態依存バイアスを統合し、共有パラメータリニアリカレンス内でExistential \textsc{\textsc{OR}}とUniversal \textsc{\textsc{AND}}アグリゲーションの表現を可能にする。
このアーキテクチャ変更は、ネットワークの計算クラスをAFAに構造的に同型にすることで、その指数的簡潔さを継承することを証明している。
我々は,LG-TS-FFNの前方通過が,瞬時$\varepsilon$-closureを含むAFAの到達可能性ダイナミクスを正確にシミュレートすることを厳密に証明する。
さらに、実験的な学習可能性を示す: 論理ゲートの連続的な緩和により、ネットワークは標準勾配降下によりバイナリラベルからオートマトントポロジと論理的意味論を同時に回復することができる。
総合的な実験により,本モデルは,統計的学習と簡潔で普遍的な論理的推論のギャップを埋めることにより,地底オートマトンを完全回復することを確認した。
関連論文リスト
- TorchLean: Formalizing Neural Networks in Lean [71.68907600404513]
本稿では,学習モデルを一級数学的対象として扱うフレームワークであるTorchLeanを紹介する。
我々はTorchLeanのエンドツーエンドを、証明された堅牢性、PINNの物理インフォームド残差、Lyapunovスタイルのニューラルコントローラ検証で検証する。
論文 参考訳（メタデータ） (2026-02-26T05:11:44Z) - A Constructive Framework for Nondeterministic Automata via Time-Shared, Depth-Unrolled Feedforward Networks [0.0]
非決定論的有限オートマトン(NFA)の時間分割・深度制御型フィードフォワードネットワーク(TS-FFN)を用いたフォーマルで建設的なシミュレーションフレームワークを提案する。
我々の定式化は、二進ベクトルとしてのオートマトン状態、スパース行列変換としての遷移、および共有しきい値更新の合成としての$varepsilon$-closuresを含む非決定的分岐を含む非決定論的分岐を象徴的に符号化する。
論文 参考訳（メタデータ） (2025-05-30T01:18:35Z) - Neural Networks as Universal Finite-State Machines: A Constructive Deterministic Finite Automaton Theory [0.0]
我々は、ユニバーサル有限状態マシン(N-FSM)としてフィードフォワードニューラルネットワークを確立する。
我々の結果は、有限深度ReLUとしきい値ネットワークが決定論的有限オートマトン(DFAs)を正確にシミュレートできることを証明している。
固定深度フィードフォワードネットワークは、メモリを必要とする非正規言語を認識できない。
論文 参考訳（メタデータ） (2025-05-16T21:01:34Z) - Understanding Token-level Topological Structures in Transformer-based Time Series Forecasting [52.364260925700485]
Transformer-based method has achieved state-of-the-art performance in time series forecasting (TSF)
既存のトランスフォーマーが中間層全体を通してトークン間の固有位相構造を完全に活用しているかどうかは不明である。
トークンレベルのトポロジを明示的にかつ適応的に保存するトランスフォーマーベースの新しいTSF手法であるトポロジ拡張法(TEM)を提案する。
論文 参考訳（メタデータ） (2024-04-16T07:21:39Z) - LOGICSEG: Parsing Visual Semantics with Neural Logic Learning and
Reasoning [73.98142349171552]
LOGICSEGは、神経誘導学習と論理推論をリッチデータとシンボリック知識の両方に統合する、全体論的視覚意味論である。
ファジィ論理に基づく連続的な緩和の間、論理式はデータとニューラルな計算グラフに基礎を置いており、論理によるネットワークトレーニングを可能にする。
これらの設計によりLOGICSEGは、既存のセグメンテーションモデルに容易に統合できる汎用的でコンパクトなニューラル論理マシンとなる。
論文 参考訳（メタデータ） (2023-09-24T05:43:19Z) - Pretraining Graph Neural Networks for few-shot Analog Circuit Modeling
and Design [68.1682448368636]
本稿では、新しい未知のトポロジや未知の予測タスクに適応可能な回路表現を学習するための教師付き事前学習手法を提案する。
異なる回路の変動位相構造に対処するため、各回路をグラフとして記述し、グラフニューラルネットワーク(GNN)を用いてノード埋め込みを学習する。
出力ノード電圧の予測における事前学習GNNは、新しい未知のトポロジや新しい回路レベル特性の予測に適応可能な学習表現を促進することができることを示す。
論文 参考訳（メタデータ） (2022-03-29T21:18:47Z) - Connecting Weighted Automata, Tensor Networks and Recurrent Neural
Networks through Spectral Learning [58.14930566993063]
我々は、形式言語と言語学からの重み付き有限オートマトン(WFA)、機械学習で使用されるリカレントニューラルネットワーク、テンソルネットワークの3つのモデル間の接続を提示する。
本稿では,連続ベクトル入力の列上に定義された線形2-RNNに対する最初の証明可能な学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-10-19T15:28:00Z) - Logical Natural Language Generation from Open-Domain Tables [107.04385677577862]
本稿では,その事実に関連付けられた自然言語文をモデルで生成するタスクを提案する。
提案した論理的 NLG 問題の研究を容易にするために,幅広い論理的・記号的推論を特徴とする既存の TabFact データセットcitechen 2019tabfact を用いる。
新しいタスクは、シーケンス順序と論理順序のミスマッチのため、既存のモノトニック生成フレームワークに課題をもたらす。
論文 参考訳（メタデータ） (2020-04-22T06:03:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。