# Logic-Gated Time-Shared Feedforward Networks for Alternating Finite Automata: Exact Simulation and Learnability

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 29 of its 60 references that are in the map.
- First posted on arXiv 20 Mar 2026.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification](https://mlsanity.com/paper/1502.01852/) (2015)
- [Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation](https://mlsanity.com/paper/1308.3432/) (2013)
- [DARTS: Differentiable Architecture Search](https://mlsanity.com/paper/1806.09055/) (2018)
- [Combining Recurrent, Convolutional, and Continuous-time Models with Linear State-Space Layers](https://mlsanity.com/paper/2110.13985/) (2021)
- [SNAS: Stochastic Neural Architecture Search](https://mlsanity.com/paper/1812.09926/) (2018)
- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [Learning Explanatory Rules from Noisy Data](https://mlsanity.com/paper/1711.04574/) (2017)
- [Learning a SAT Solver from Single-Bit Supervision](https://mlsanity.com/paper/1802.03685/) (2018)
- [Efficient Formal Safety Analysis of Neural Networks](https://mlsanity.com/paper/1809.08098/) (2018)
- [Neural Logic Machines](https://mlsanity.com/paper/1904.11694/) (2019)
- [Logic Tensor Networks for Semantic Image Interpretation](https://mlsanity.com/paper/1705.08968/) (2017)
- [Extracting Automata from Recurrent Neural Networks Using Queries and Counterexamples](https://mlsanity.com/paper/1711.09576/) (2017)
- [A Formal Hierarchy of RNN Architectures](https://mlsanity.com/paper/2004.08500/) (2020)
- [Sequential Neural Networks as Automata](https://mlsanity.com/paper/1906.01615/) (2019)
- [The Expressive Capacity of State Space Models: A Formal Language Perspective](https://mlsanity.com/paper/2405.17394/) (2024)
- [Differentiable Sorting Networks for Scalable Sorting and Ranking Supervision](https://mlsanity.com/paper/2105.04019/) (2021)
- [On the Expressiveness and Length Generalization of Selective State-Space Models on Regular Languages](https://mlsanity.com/paper/2412.19350/) (2024)
- [Neural Network Verification is a Programming Language Challenge](https://mlsanity.com/paper/2501.05867/) (2025)
- [Differentiable Logic Cellular Automata: From Game of Life to Pattern Generation](https://mlsanity.com/paper/2506.04912/) (2025)
- [Neural Model Checking](https://mlsanity.com/paper/2410.23790/) (2024)
- [Transformers are Inherently Succinct](https://mlsanity.com/paper/2510.19315/) (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)
- [RNN Generalization to Omega-Regular Languages](https://mlsanity.com/paper/2509.02491/) (2025)
- [Symbolic Feedforward Networks for Probabilistic Finite Automata: Exact Simulation and Learnability](https://mlsanity.com/paper/2509.10034/) (2025)
- [Warm Starting State-Space Models with Automata Learning](https://mlsanity.com/paper/2603.05694/) (2026)

## Abstract (arXiv)

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 textsctextscOR and Universal textsctextscAND 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 2n 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.