Neural Networks as Universal Finite-State Machines: A Constructive Feedforward Simulation Framework for NFAs

• URL: http://arxiv.org/abs/2505.24110v3
• Date: Mon, 04 Aug 2025 04:35:00 GMT
• Title: Neural Networks as Universal Finite-State Machines: A Constructive Feedforward Simulation Framework for NFAs
• Authors: Sahil Rajesh Dhayalkar,
• Abstract summary: This work establishes a new bridge between symbolic automata theory and modern neural architectures.<n>We show that feedforward networks can perform precise, interpretable, and trainable symbolic computation.
• Score: 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 standard feedforward neural networks. Unlike prior approaches that rely on 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 a depth-unrolled feedforward network with shared parameters, independent of input length. Our construction yields not only formal equivalence between NFAs and neural networks, but also practical trainability: we demonstrate that these networks can learn NFA acceptance behavior through gradient descent using standard supervised data. Extensive experiments validate all theoretical results, achieving perfect or near-perfect agreement on acceptance, state propagation, and closure dynamics. This work establishes a new bridge between symbolic automata theory and modern neural architectures, showing that feedforward networks can perform precise, interpretable, and trainable symbolic computation.

Related papers

• Neural Networks as Universal Finite-State Machines: A Constructive Deterministic Finite Automaton Theory [0.0]
  We establish feedforward neural networks as universal finite-state machines (N-FSMs)<n>Our results prove that finite-depth ReLU and threshold networks can exactly simulate deterministic finite automata (DFAs)<n>We formalize the expressivity boundary: fixed-depth feedforward networks cannot recognize non-regular languages requiring memory.
  arXiv  Detail & Related papers  (2025-05-16T21:01:34Z)
• Deriving Equivalent Symbol-Based Decision Models from Feedforward Neural Networks [0.0]
  Despite its rapid adoption, the opacity of AI systems poses significant challenges to trust and acceptance.<n>This work focuses on the derivation of symbolic models, such as decision trees, from feed-forward neural networks (FNNs)
  arXiv  Detail & Related papers  (2025-04-16T19:22:53Z)
• Enhancing lattice kinetic schemes for fluid dynamics with Lattice-Equivariant Neural Networks [79.16635054977068]
  We present a new class of equivariant neural networks, dubbed Lattice-Equivariant Neural Networks (LENNs) Our approach develops within a recently introduced framework aimed at learning neural network-based surrogate models Lattice Boltzmann collision operators. Our work opens towards practical utilization of machine learning-augmented Lattice Boltzmann CFD in real-world simulations.
  arXiv  Detail & Related papers  (2024-05-22T17:23:15Z)
• Lipschitz constant estimation for general neural network architectures using control tools [0.05120567378386613]
  This paper is devoted to the estimation of the Lipschitz constant of general neural network architectures using semidefinite programming. We interpret neural networks as time-varying dynamical systems, where the $k$th layer corresponds to the dynamics at time $k$.
  arXiv  Detail & Related papers  (2024-05-02T09:38:16Z)
• From NeurODEs to AutoencODEs: a mean-field control framework for width-varying Neural Networks [68.8204255655161]
  We propose a new type of continuous-time control system, called AutoencODE, based on a controlled field that drives dynamics. We show that many architectures can be recovered in regions where the loss function is locally convex.
  arXiv  Detail & Related papers  (2023-07-05T13:26:17Z)
• Set-based Neural Network Encoding Without Weight Tying [91.37161634310819]
  We propose a neural network weight encoding method for network property prediction.<n>Our approach is capable of encoding neural networks in a model zoo of mixed architecture.<n>We introduce two new tasks for neural network property prediction: cross-dataset and cross-architecture.
  arXiv  Detail & Related papers  (2023-05-26T04:34:28Z)
• Asymmetric Certified Robustness via Feature-Convex Neural Networks [11.605936648692543]
  We show that an ICNN can be generalizationd to an adversarial network. Experiments show that the network is far more efficient than any competitive baseline.
  arXiv  Detail & Related papers  (2023-02-03T19:17:28Z)
• Symbolic Distillation for Learned TCP Congestion Control [70.27367981153299]
  TCP congestion control has achieved tremendous success with deep reinforcement learning (RL) approaches. Black-box policies lack interpretability and reliability, and often, they need to operate outside the traditional TCP datapath. This paper proposes a novel two-stage solution to achieve the best of both worlds: first, to train a deep RL agent, then distill its NN policy into white-box, light-weight rules.
  arXiv  Detail & Related papers  (2022-10-24T00:58:16Z)
• Signal Processing for Implicit Neural Representations [80.38097216996164]
  Implicit Neural Representations (INRs) encode continuous multi-media data via multi-layer perceptrons. Existing works manipulate such continuous representations via processing on their discretized instance. We propose an implicit neural signal processing network, dubbed INSP-Net, via differential operators on INR.
  arXiv  Detail & Related papers  (2022-10-17T06:29:07Z)
• Robust Training and Verification of Implicit Neural Networks: A Non-Euclidean Contractive Approach [64.23331120621118]
  This paper proposes a theoretical and computational framework for training and robustness verification of implicit neural networks. We introduce a related embedded network and show that the embedded network can be used to provide an $ell_infty$-norm box over-approximation of the reachable sets of the original network. We apply our algorithms to train implicit neural networks on the MNIST dataset and compare the robustness of our models with the models trained via existing approaches in the literature.
  arXiv  Detail & Related papers  (2022-08-08T03:13:24Z)
• On the Effective Number of Linear Regions in Shallow Univariate ReLU Networks: Convergence Guarantees and Implicit Bias [50.84569563188485]
  We show that gradient flow converges in direction when labels are determined by the sign of a target network with $r$ neurons. Our result may already hold for mild over- parameterization, where the width is $tildemathcalO(r)$ and independent of the sample size.
  arXiv  Detail & Related papers  (2022-05-18T16:57:10Z)
• Modeling Structure with Undirected Neural Networks [20.506232306308977]
  We propose undirected neural networks, a flexible framework for specifying computations that can be performed in any order. We demonstrate the effectiveness of undirected neural architectures, both unstructured and structured, on a range of tasks.
  arXiv  Detail & Related papers  (2022-02-08T10:06:51Z)
• Integrating Regular Expressions with Neural Networks via DFA [40.09868407372605]
  It is very important to integrate the rule knowledge into neural networks to build a hybrid model that achieves better performance. Specifically, the human-designed rules are formulated as Regular Expressions (REs) We propose to use the MDFA as an intermediate model to capture the matched RE patterns as rule-based features for each input sentence.
  arXiv  Detail & Related papers  (2021-09-07T05:48:51Z)
• FF-NSL: Feed-Forward Neural-Symbolic Learner [70.978007919101]
  This paper introduces a neural-symbolic learning framework, called Feed-Forward Neural-Symbolic Learner (FF-NSL) FF-NSL integrates state-of-the-art ILP systems based on the Answer Set semantics, with neural networks, in order to learn interpretable hypotheses from labelled unstructured data.
  arXiv  Detail & Related papers  (2021-06-24T15:38:34Z)
• Connecting Weighted Automata, Tensor Networks and Recurrent Neural Networks through Spectral Learning [58.14930566993063]
  We present connections between three models used in different research fields: weighted finite automata(WFA) from formal languages and linguistics, recurrent neural networks used in machine learning, and tensor networks. We introduce the first provable learning algorithm for linear 2-RNN defined over sequences of continuous vectors input.
  arXiv  Detail & Related papers  (2020-10-19T15:28:00Z)
• Provably Efficient Neural Estimation of Structural Equation Model: An Adversarial Approach [144.21892195917758]
  We study estimation in a class of generalized Structural equation models (SEMs) We formulate the linear operator equation as a min-max game, where both players are parameterized by neural networks (NNs), and learn the parameters of these neural networks using a gradient descent. For the first time we provide a tractable estimation procedure for SEMs based on NNs with provable convergence and without the need for sample splitting.
  arXiv  Detail & Related papers  (2020-07-02T17:55:47Z)
• Investigating the Compositional Structure Of Deep Neural Networks [1.8899300124593645]
  We introduce a novel theoretical framework based on the compositional structure of piecewise linear activation functions. It is possible to characterize the instances of the input data with respect to both the predicted label and the specific (linear) transformation used to perform predictions. Preliminary tests on the MNIST dataset show that our method can group input instances with regard to their similarity in the internal representation of the neural network.
  arXiv  Detail & Related papers  (2020-02-17T14:16:17Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.