論文の概要: A Constructive Framework for Nondeterministic Automata via Time-Shared, Depth-Unrolled Feedforward Networks

• arxiv url: http://arxiv.org/abs/2505.24110v4
• Date: Fri, 10 Oct 2025 01:03:04 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-14 00:38:45.504408
• Title: A Constructive Framework for Nondeterministic Automata via Time-Shared, Depth-Unrolled Feedforward Networks
• Title（参考訳）: 非決定論的オートマトンのための時間的・深さ的なフィードフォワードネットワークによる構成的フレームワーク
• Authors: Sahil Rajesh Dhayalkar,
• Abstract要約: 非決定論的有限オートマトン(NFA)の時間分割・深度制御型フィードフォワードネットワーク(TS-FFN)を用いたフォーマルで建設的なシミュレーションフレームワークを提案する。 我々の定式化は、二進ベクトルとしてのオートマトン状態、スパース行列変換としての遷移、および共有しきい値更新の合成としての$varepsilon$-closuresを含む非決定的分岐を含む非決定論的分岐を象徴的に符号化する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present a formal and constructive simulation framework for nondeterministic finite automata (NFAs) using time-shared, depth-unrolled feedforward networks (TS-FFNs), i.e., acyclic unrolled computations with shared parameters that are functionally equivalent to unrolled recurrent or state-space models. Unlike prior approaches that rely on explicit recurrent architectures or post hoc extraction methods, our formulation symbolically encodes automaton states as binary vectors, transitions as sparse matrix transformations, and nondeterministic branching-including $\varepsilon$-closures-as compositions of shared thresholded updates. We prove that every regular language can be recognized exactly by such a shared-parameter unrolled feedforward network, with parameter count independent of input length. Our construction yields a constructive equivalence between NFAs and neural networks and demonstrates \emph{empirical learnability}: these networks can be trained via gradient descent on supervised acceptance data to recover the target automaton behavior. This learnability, formalized in Proposition 5.1, is the crux of this work. Extensive experiments validate the theoretical results, achieving perfect or near-perfect agreement on acceptance, state propagation, and closure dynamics. This work clarifies the correspondence between automata theory and modern neural architectures, showing that unrolled feedforward networks can perform precise, interpretable, and trainable symbolic computation.
• Abstract（参考訳）: 本研究では,非決定論的有限オートマトン (NFA) のための形式的・構成的なシミュレーションフレームワークを提案する。 明示的なリカレントアーキテクチャやポストホック抽出手法に依存する従来のアプローチとは異なり、我々の定式化では、オートマトン状態を二進ベクトル、スパース行列変換としての遷移、および共有しきい値更新の合成としての$\varepsilon$-closuresを含む非決定的分岐を象徴的に符号化している。 パラメータ数が入力長に依存しないような共有パラメータアンロールフィードフォワードネットワークによって、すべての正規言語を正確に認識できることを実証する。 我々の構築は,NFAとニューラルネットワーク間の構築的等価性を示し,これらのネットワークは,教師付き受入データに基づく勾配勾配によるトレーニングにより,対象のオートマトン行動の回復を可能にする。 この学習性は命題5.1で定式化され、この研究の要点である。 広範な実験により理論結果が検証され、受容、状態伝播、閉包力学に関する完全あるいはほぼ完全な合意が達成される。 この研究は、オートマトン理論と現代のニューラルアーキテクチャの対応を明確にし、アンロールされたフィードフォワードネットワークが正確で解釈可能で、訓練可能なシンボル計算を実行可能であることを示した。

関連論文リスト

• TorchLean: Formalizing Neural Networks in Lean [71.68907600404513]
  本稿では,学習モデルを一級数学的対象として扱うフレームワークであるTorchLeanを紹介する。 我々はTorchLeanのエンドツーエンドを、証明された堅牢性、PINNの物理インフォームド残差、Lyapunovスタイルのニューラルコントローラ検証で検証する。
  論文  参考訳（メタデータ） (2026-02-26T05:11:44Z)
• Smooth embeddings in contracting recurrent networks driven by regular dynamics: A synthesis for neural representation [45.88028371034407]
  最近の実証研究は、訓練された反復モデルにおけるトポロジー保存潜在組織を文書化している。 貯水池計算における最近の理論的結果は、同期写像が埋め込みである条件を確立する。 私たちのコントリビューションは、一般的な同期と、契約型貯水池の埋め込み保証を組み立てる統合フレームワークです。
  論文  参考訳（メタデータ） (2026-01-26T23:10:39Z)
• Extracting Robust Register Automata from Neural Networks over Data Sequences [1.7959033226568346]
  既存の技法は有限入力アルファベットを仮定するので、連続領域から引き出されたデータシーケンスには直接適用できない。 この課題は、有限オートマトンを数値を格納・比較するレジスタで拡張する決定論的レジスタオートマトン(DRAs)を用いて解決する。 我々の主な貢献は、ブラックボックスモデルから堅牢なDRA抽出のためのフレームワークである。
  論文  参考訳（メタデータ） (2025-11-24T13:36:45Z)
• Symbolic Feedforward Networks for Probabilistic Finite Automata: Exact Simulation and Learnability [0.0]
  確率的有限オートマトンは、シンボルフィードフォワードニューラルネットワークを用いて正確にシミュレートできることを示す。 これらの記号シミュレータは表現性だけでなく学習性にも優れることを示す。
  論文  参考訳（メタデータ） (2025-09-12T07:57:01Z)
• Neural Networks as Universal Finite-State Machines: A Constructive Deterministic Finite Automaton Theory [0.0]
  我々は、ユニバーサル有限状態マシン(N-FSM)としてフィードフォワードニューラルネットワークを確立する。 我々の結果は、有限深度ReLUとしきい値ネットワークが決定論的有限オートマトン(DFAs)を正確にシミュレートできることを証明している。 固定深度フィードフォワードネットワークは、メモリを必要とする非正規言語を認識できない。
  論文  参考訳（メタデータ） (2025-05-16T21:01:34Z)
• Deriving Equivalent Symbol-Based Decision Models from Feedforward Neural Networks [0.0]
  急速な採用にもかかわらず、AIシステムの不透明さは、信頼と受け入れに重大な課題をもたらす。 この研究は、フィードフォワードニューラルネットワーク(FNN)から決定木などのシンボルモデルの導出に焦点を当てている。
  論文  参考訳（メタデータ） (2025-04-16T19:22:53Z)
• 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)
• Semantic Loss Functions for Neuro-Symbolic Structured Prediction [74.18322585177832]
  このような構造に関する知識を象徴的に定義した意味的損失をトレーニングに注入する。 記号の配置に非依存であり、それによって表現される意味論にのみ依存する。 識別型ニューラルモデルと生成型ニューラルモデルの両方と組み合わせることができる。
  論文  参考訳（メタデータ） (2024-05-12T22:18:25Z)
• Lipschitz constant estimation for general neural network architectures using control tools [0.05120567378386613]
  本稿では,半定値プログラミングを用いた一般ニューラルネットワークアーキテクチャのリプシッツ定数の推定について述べる。 我々はニューラルネットワークを時間変動力学系と解釈し、そこでは、$k$th層は、時間で$k$の力学に対応する。
  論文  参考訳（メタデータ） (2024-05-02T09:38:16Z)
• Leveraging Low-Rank and Sparse Recurrent Connectivity for Robust Closed-Loop Control [63.310780486820796]
  繰り返し接続のパラメータ化が閉ループ設定のロバスト性にどのように影響するかを示す。 パラメータが少ないクローズドフォーム連続時間ニューラルネットワーク(CfCs)は、フルランクで完全に接続されたニューラルネットワークよりも優れています。
  論文  参考訳（メタデータ） (2023-10-05T21:44:18Z)
• Tractable Bounding of Counterfactual Queries by Knowledge Compilation [51.47174989680976]
  本稿では, パール構造因果モデルにおいて, 因果関係などの部分的特定可能なクエリのバウンダリングの問題について議論する。 最近提案された反復EMスキームは初期化パラメータをサンプリングしてそれらの境界を内部近似する。 シンボルパラメータを実際の値に置き換えた回路構造を,単一のシンボル知識コンパイルによって得られることを示す。
  論文  参考訳（メタデータ） (2023-10-05T07:10:40Z)
• From NeurODEs to AutoencODEs: a mean-field control framework for width-varying Neural Networks [68.8204255655161]
  本稿では,動的に駆動する制御フィールドをベースとした,AutoencODEと呼ばれる新しいタイプの連続時間制御システムを提案する。 損失関数が局所凸な領域では,多くのアーキテクチャが復元可能であることを示す。
  論文  参考訳（メタデータ） (2023-07-05T13:26:17Z)
• Set-based Neural Network Encoding Without Weight Tying [91.37161634310819]
  本稿では,ネットワーク特性予測のためのニューラルネットワーク重み符号化手法を提案する。 我々のアプローチは、混合アーキテクチャのモデル動物園でニューラルネットワークを符号化することができる。 ニューラルネットワークのプロパティ予測には,クロスデータセットとクロスアーキテクチャという,2つの新しいタスクを導入する。
  論文  参考訳（メタデータ） (2023-05-26T04:34:28Z)
• Asymmetric Certified Robustness via Feature-Convex Neural Networks [11.605936648692543]
  ICNNを敵ネットワークに一般化できることを示す。 実験により、ネットワークはどの競争ベースラインよりもはるかに効率的であることが示されている。
  論文  参考訳（メタデータ） (2023-02-03T19:17:28Z)
• Symbolic Distillation for Learned TCP Congestion Control [70.27367981153299]
  TCP渋滞制御は、深層強化学習(RL)アプローチで大きな成功を収めた。 ブラックボックスポリシーは解釈可能性と信頼性に欠けており、しばしば従来のTCPデータパスの外で運用する必要がある。 本稿では,まず深部RLエージェントを訓練し,次にNNポリシーをホワイトボックスの軽量なルールに蒸留する,両世界の長所を達成するための新しい2段階のソリューションを提案する。
  論文  参考訳（メタデータ） (2022-10-24T00:58:16Z)
• Signal Processing for Implicit Neural Representations [80.38097216996164]
  Inlicit Neural Representation (INR)は、マルチ層パーセプトロンを介して連続したマルチメディアデータを符号化する。 既存の作業は、その離散化されたインスタンスの処理を通じて、そのような連続的な表現を操作する。 本稿では,INSP-Netと呼ばれる暗黙的ニューラル信号処理ネットワークを提案する。
  論文  参考訳（メタデータ） (2022-10-17T06:29:07Z)
• 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)
• Modeling Structure with Undirected Neural Networks [20.506232306308977]
  任意の順序で実行できる計算を指定するためのフレキシブルなフレームワークである、非指向型ニューラルネットワークを提案する。 さまざまなタスクにおいて、非構造的かつ構造化された非指向型ニューラルアーキテクチャの有効性を実証する。
  論文  参考訳（メタデータ） (2022-02-08T10:06:51Z)
• Latent Network Embedding via Adversarial Auto-encoders [15.656374849760734]
  本稿では,逆グラフ自動エンコーダに基づく潜在ネットワーク埋め込みモデルを提案する。 この枠組みの下では、潜伏構造を発見する問題は、部分的な観測から潜伏関係を推測するものとして定式化されている。
  論文  参考訳（メタデータ） (2021-09-30T16:49:46Z)
• Integrating Regular Expressions with Neural Networks via DFA [40.09868407372605]
  より優れたパフォーマンスを実現するハイブリッドモデルを構築するためには、ルール知識をニューラルネットワークに統合することが非常に重要です。 具体的には、人間設計規則は正規表現(res)として定式化される。 本稿では、MDFAを中間モデルとして用いて、一致したREパターンを各入力文のルールベースの特徴として捉えることを提案する。
  論文  参考訳（メタデータ） (2021-09-07T05:48:51Z)
• FF-NSL: Feed-Forward Neural-Symbolic Learner [70.978007919101]
  本稿では,Feed-Forward Neural-Symbolic Learner (FF-NSL) と呼ばれるニューラルシンボリック学習フレームワークを紹介する。 FF-NSLは、ラベル付き非構造化データから解釈可能な仮説を学習するために、Answer Setセマンティクスに基づく最先端のICPシステムとニューラルネットワークを統合する。
  論文  参考訳（メタデータ） (2021-06-24T15:38:34Z)
• CREPO: An Open Repository to Benchmark Credal Network Algorithms [78.79752265884109]
  クレダルネットワークは、確率質量関数の集合であるクレダルに基づく不正確な確率的グラフィカルモデルである。 CREMAと呼ばれるJavaライブラリが最近リリースされ、クレダルネットワークをモデル化し、処理し、クエリする。 我々は,これらのモデル上での推論タスクの正確な結果とともに,合成クレダルネットワークのオープンリポジトリであるcrrepoを提案する。
  論文  参考訳（メタデータ） (2021-05-10T07:31:59Z)
• DAIS: Automatic Channel Pruning via Differentiable Annealing Indicator Search [55.164053971213576]
  畳み込みニューラルネットワークは,計算オーバーヘッドが大きいにもかかわらず,コンピュータビジョンタスクの実行において大きな成功を収めている。 構造的(チャネル)プルーニングは、通常、ネットワーク構造を保ちながらモデルの冗長性を低減するために適用される。 既存の構造化プルーニング法では、手作りのルールが必要であり、これは大きなプルーニング空間に繋がる可能性がある。
  論文  参考訳（メタデータ） (2020-11-04T07:43:01Z)
• 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)
• Investigating the Compositional Structure Of Deep Neural Networks [1.8899300124593645]
  本稿では,一方向線形活性化関数の構成構造に基づく新しい理論的枠組みを提案する。 予測ラベルと予測に使用する特定の(線形)変換の両方に関して、入力データのインスタンスを特徴付けることができる。 MNISTデータセットの予備テストでは、ニューラルネットワークの内部表現における類似性に関して、入力インスタンスをグループ化することが可能である。
  論文  参考訳（メタデータ） (2020-02-17T14:16:17Z)

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

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