論文の概要: Neural Networks as Universal Finite-State Machines: A Constructive ReLU Simulation Framework for NFAs

• arxiv url: http://arxiv.org/abs/2505.24110v1
• Date: Fri, 30 May 2025 01:18:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-02 19:47:52.721893
• Title: Neural Networks as Universal Finite-State Machines: A Constructive ReLU Simulation Framework for NFAs
• Title（参考訳）: 汎用有限状態マシンとしてのニューラルネットワーク:NFAのための構成型ReLUシミュレーションフレームワーク
• Authors: Sahil Rajesh Dhayalkar,
• Abstract要約: ReLUアクティベーションは非決定論的分岐、サブセット構成、および$epsilon$-クロージャを数学的に正確にシミュレートする。 この研究は、標準ディープラーニングアーキテクチャにおけるNFAの証明可能な完全なシンボルシミュレーションを初めて提供する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present a formal and constructive framework establishing the equivalence between nondeterministic finite automata (NFAs) and standard feedforward ReLU neural networks. By encoding automaton states as binary vectors and transitions as sparse linear layers, we show that ReLU activations simulate nondeterministic branching, subset construction, and $\epsilon$-closures in a mathematically precise manner. Our core theoretical results prove that a three-layer ReLU network of width $\mathcal{O}(n)$ can exactly recognize any regular language accepted by an $n$-state NFA-without recurrence, memory, or approximation. Furthermore, we show that gradient descent over structure-preserving networks preserves symbolic semantics and acceptance behavior. Extensive experiments across multiple validation tasks-including parallel path tracking, symbolic subset construction, $\epsilon$-closure convergence, acceptance classification, structural training invariants, and functional equivalence-achieve perfect or near-perfect empirical alignment with ground-truth automata. This work provides the first provably complete symbolic simulation of NFAs within standard deep learning architectures, uniting automata theory with neural computation through ReLU dynamics.
• Abstract（参考訳）: 非決定論的有限オートマトン(NFA)と標準フィードフォワードReLUニューラルネットワークの等価性を確立するための形式的,建設的な枠組みを提案する。 オートマトン状態を二項ベクトルとして符号化し、疎線型層として遷移することにより、ReLU活性化が非決定的分岐、部分集合構成、および$\epsilon$-クロージャを数学的に正確にシミュレートすることを示す。 我々の中核的な理論的結果は、$\mathcal{O}(n)$の3層ReLUネットワークが、再帰、記憶、近似なしに$n$状態のNFAで受け入れられる正規言語を正確に認識できることを証明している。 さらに, 構造保存ネットワークに対する勾配勾配は, 象徴的意味論と受容行動を保存することを示す。 並列経路追跡、シンボリックサブセット構成、$\epsilon$-closureコンバージェンス、受け入れ分類、構造的訓練不変量、機能的同値化の完全あるいはほぼ完全な実験的アライメントを含む複数の検証タスクにわたる広範な実験。 この研究は、標準ディープラーニングアーキテクチャにおけるNFAの証明可能な完全なシンボリックシミュレーションを初めて提供し、ReLUダイナミクスを通じてオートマトン理論とニューラル計算を結合した。

関連論文リスト

• Neural Networks as Universal Finite-State Machines: A Constructive Deterministic Finite Automaton Theory [0.0]
  我々は、ユニバーサル有限状態マシン(N-FSM)としてフィードフォワードニューラルネットワークを確立する。 我々の結果は、有限深度ReLUとしきい値ネットワークが決定論的有限オートマトン(DFAs)を正確にシミュレートできることを証明している。 固定深度フィードフォワードネットワークは、メモリを必要とする非正規言語を認識できない。
  論文  参考訳（メタデータ） (2025-05-16T21:01:34Z)
• Enhancing lattice kinetic schemes for fluid dynamics with Lattice-Equivariant Neural Networks [79.16635054977068]
  我々はLattice-Equivariant Neural Networks (LENNs)と呼ばれる新しい同変ニューラルネットワークのクラスを提案する。 我々の手法は、ニューラルネットワークに基づく代理モデルLattice Boltzmann衝突作用素の学習を目的とした、最近導入されたフレームワーク内で開発されている。 本研究は,実世界のシミュレーションにおける機械学習強化Lattice Boltzmann CFDの実用化に向けて展開する。
  論文  参考訳（メタデータ） (2024-05-22T17:23:15Z)
• Lipschitz constant estimation for general neural network architectures using control tools [0.05120567378386613]
  本稿では,半定値プログラミングを用いた一般ニューラルネットワークアーキテクチャのリプシッツ定数の推定について述べる。 我々はニューラルネットワークを時間変動力学系と解釈し、そこでは、$k$th層は、時間で$k$の力学に対応する。
  論文  参考訳（メタデータ） (2024-05-02T09:38:16Z)
• From NeurODEs to AutoencODEs: a mean-field control framework for width-varying Neural Networks [68.8204255655161]
  本稿では,動的に駆動する制御フィールドをベースとした,AutoencODEと呼ばれる新しいタイプの連続時間制御システムを提案する。 損失関数が局所凸な領域では,多くのアーキテクチャが復元可能であることを示す。
  論文  参考訳（メタデータ） (2023-07-05T13:26:17Z)
• Asymmetric Certified Robustness via Feature-Convex Neural Networks [11.605936648692543]
  ICNNを敵ネットワークに一般化できることを示す。 実験により、ネットワークはどの競争ベースラインよりもはるかに効率的であることが示されている。
  論文  参考訳（メタデータ） (2023-02-03T19:17:28Z)
• Robust Training and Verification of Implicit Neural Networks: A Non-Euclidean Contractive Approach [64.23331120621118]
  本稿では,暗黙的ニューラルネットワークのトレーニングとロバスト性検証のための理論的および計算的枠組みを提案する。 組込みネットワークを導入し、組込みネットワークを用いて、元のネットワークの到達可能な集合の超近似として$ell_infty$-normボックスを提供することを示す。 MNISTデータセット上で暗黙的なニューラルネットワークをトレーニングするためにアルゴリズムを適用し、我々のモデルの堅牢性と、文献における既存のアプローチを通じてトレーニングされたモデルを比較する。
  論文  参考訳（メタデータ） (2022-08-08T03:13:24Z)
• On the Effective Number of Linear Regions in Shallow Univariate ReLU Networks: Convergence Guarantees and Implicit Bias [50.84569563188485]
  我々は、ラベルが$r$のニューロンを持つターゲットネットワークの符号によって決定されるとき、勾配流が方向収束することを示す。 我々の結果は、標本サイズによらず、幅が$tildemathcalO(r)$である、緩やかなオーバーパラメータ化をすでに維持しているかもしれない。
  論文  参考訳（メタデータ） (2022-05-18T16:57:10Z)
• Connecting Weighted Automata, Tensor Networks and Recurrent Neural Networks through Spectral Learning [58.14930566993063]
  我々は、形式言語と言語学からの重み付き有限オートマトン(WFA)、機械学習で使用されるリカレントニューラルネットワーク、テンソルネットワークの3つのモデル間の接続を提示する。 本稿では,連続ベクトル入力の列上に定義された線形2-RNNに対する最初の証明可能な学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-10-19T15:28:00Z)
• Provably Efficient Neural Estimation of Structural Equation Model: An Adversarial Approach [144.21892195917758]
  一般化構造方程式モデル(SEM)のクラスにおける推定について検討する。 線形作用素方程式をmin-maxゲームとして定式化し、ニューラルネットワーク(NN)でパラメータ化し、勾配勾配を用いてニューラルネットワークのパラメータを学習する。 提案手法は,サンプル分割を必要とせず,確固とした収束性を持つNNをベースとしたSEMの抽出可能な推定手順を初めて提供する。
  論文  参考訳（メタデータ） (2020-07-02T17:55:47Z)

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

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