# Symbolic Feedforward Networks for Probabilistic Finite Automata: Exact Simulation and Learnability

arXiv: https://arxiv.org/abs/2509.10034 · HTML: https://mlsanity.com/paper/2509.10034/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 36 references that are in the map.
- First posted on arXiv 12 Sep 2025.

## Builds on (most cited first, 22 of 22)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Neural Turing Machines](https://mlsanity.com/paper/1410.5401/) (2014)
- [Adaptive Computation Time for Recurrent Neural Networks](https://mlsanity.com/paper/1603.08983/) (2016)
- [In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning](https://mlsanity.com/paper/1412.6614/) (2014)
- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [Compositionality decomposed: how do neural networks generalise?](https://mlsanity.com/paper/1908.08351/) (2019)
- [Neural-Symbolic Learning and Reasoning: A Survey and Interpretation](https://mlsanity.com/paper/1711.03902/) (2017)
- [End-to-End Differentiable Proving](https://mlsanity.com/paper/1705.11040/) (2017)
- [Neural-Symbolic Computing: An Effective Methodology for Principled Integration of Machine Learning and Reasoning](https://mlsanity.com/paper/1905.06088/) (2019)
- [Approximating Continuous Functions by ReLU Nets of Minimal Width](https://mlsanity.com/paper/1710.11278/) (2017)
- [Abstract Syntax Networks for Code Generation and Semantic Parsing](https://mlsanity.com/paper/1704.07535/) (2017)
- [Extracting Automata from Recurrent Neural Networks Using Queries and Counterexamples](https://mlsanity.com/paper/1711.09576/) (2017)
- [Learning to Remember Rare Events](https://mlsanity.com/paper/1703.03129/) (2017)
- [Training Neural Networks as Recognizers of Formal Languages](https://mlsanity.com/paper/2411.07107/) (2024)
- [Extracting Weighted Finite Automata from Recurrent Neural Networks for Natural Languages](https://mlsanity.com/paper/2206.14621/) (2022)
- [Representing Formal Languages: A Comparison Between Finite Automata and Recurrent Neural Networks](https://mlsanity.com/paper/1902.10297/) (2019)
- [Learning Halfspaces and Neural Networks with Random Initialization](https://mlsanity.com/paper/1511.07948/) (2015)
- [The Geometry of ReLU Networks through the ReLU Transition Graph](https://mlsanity.com/paper/2505.11692/) (2025)
- [A Combinatorial Theory of Dropout: Subnetworks, Graph Geometry, and Generalization](https://mlsanity.com/paper/2504.14762/) (2025)
- [Neural Networks as Universal Finite-State Machines: A Constructive Deterministic Finite Automaton Theory](https://mlsanity.com/paper/2505.11694/) (2025)
- [A Constructive Framework for Nondeterministic Automata via Time-Shared, Depth-Unrolled Feedforward Networks](https://mlsanity.com/paper/2505.24110/) (2025)
- [Probabilistic Deterministic Finite Automata and Recurrent Networks, Revisited](https://mlsanity.com/paper/1910.07663/) (2019)

## Built on by (most cited first, 1 of 1)

- [Logic-Gated Time-Shared Feedforward Networks for Alternating Finite Automata: Exact Simulation and Learnability](https://mlsanity.com/paper/2604.01228/) (2026)

## Abstract (arXiv)

We present a formal and constructive theory showing that probabilistic finite automata (PFAs) can be exactly simulated using symbolic feedforward neural networks. Our architecture represents state distributions as vectors and transitions as stochastic matrices, enabling probabilistic state propagation via matrix-vector products. This yields a parallel, interpretable, and differentiable simulation of PFA dynamics using soft updates-without recurrence. We formally characterize probabilistic subset construction, varepsilon-closure, and exact simulation via layered symbolic computation, and prove equivalence between PFAs and specific classes of neural networks. We further show that these symbolic simulators are not only expressive but learnable: trained with standard gradient descent-based optimization on labeled sequence data, they recover the exact behavior of ground-truth PFAs. This learnability, formalized in Proposition 5.1, is the crux of this work. Our results unify probabilistic automata theory with neural architectures under a rigorous algebraic framework, bridging the gap between symbolic computation and deep learning.