# DeepDFA: Automata Learning through Neural Probabilistic Relaxations

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 33 references that are in the map.
- First posted on arXiv 16 Aug 2024.

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

- [Distilling the Knowledge in a Neural Network](https://mlsanity.com/paper/1503.02531/) (2015)
- [Categorical Reparameterization with Gumbel-Softmax](https://mlsanity.com/paper/1611.01144/) (2016)
- [Neurosymbolic AI: The 3rd Wave](https://mlsanity.com/paper/2012.05876/) (2020)
- [Neural-Symbolic Learning and Reasoning: A Survey and Interpretation](https://mlsanity.com/paper/1711.03902/) (2017)
- [Extracting Automata from Recurrent Neural Networks Using Queries and Counterexamples](https://mlsanity.com/paper/1711.09576/) (2017)
- [Reinforcement Learning with Non-Markovian Rewards](https://mlsanity.com/paper/1912.02552/) (2019)
- [An Empirical Evaluation of Rule Extraction from Recurrent Neural Networks](https://mlsanity.com/paper/1709.10380/) (2017)
- [Extracting Finite Automata from RNNs Using State Merging](https://mlsanity.com/paper/2201.12451/) (2022)
- [Noisy Symbolic Abstractions for Deep RL: A case study with Reward Machines](https://mlsanity.com/paper/2211.10902/) (2022)
- [Differentiable Rule Induction with Learned Relational Features](https://mlsanity.com/paper/2201.06515/) (2022)
- [Learning Finite Linear Temporal Logic Specifications with a Specialized Neural Operator](https://mlsanity.com/paper/2111.04147/) (2021)
- [Neural-based classification rule learning for sequential data](https://mlsanity.com/paper/2302.11286/) (2023)

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

- [NeSyA: Neurosymbolic Automata](https://mlsanity.com/paper/2412.07331/) (2024)
- [Neuro-Symbolic Predictive Process Monitoring](https://mlsanity.com/paper/2509.00834/) (2025)
- [T-ILR: a Neurosymbolic Integration for LTLf](https://mlsanity.com/paper/2508.15943/) (2025)
- [A Neuro-Symbolic Framework for Sequence Classification with Relational and Temporal Knowledge](https://mlsanity.com/paper/2505.05106/) (2025)
- [PrefixGuard: From LLM-Agent Traces to Online Failure-Warning Monitors](https://mlsanity.com/paper/2605.06455/) (2026)
- [DeepDFA: Injecting Temporal Logic in Deep Learning for Sequential Subsymbolic Applications](https://mlsanity.com/paper/2602.03486/) (2026)
- [Neuro-Symbolic Injection of LTLf Constraints in Autoregressive Reinforcement Learning Policies](https://mlsanity.com/paper/2606.08312/) (2026)
- [Exact Distinguishability in Non-Markovian Decision Processes](https://mlsanity.com/paper/2610.01527/) (2026)

## Abstract (arXiv)

In this work, we introduce DeepDFA, a novel approach to identifying Deterministic Finite Automata (DFAs) from traces, harnessing a differentiable yet discrete model. Inspired by both the probabilistic relaxation of DFAs and Recurrent Neural Networks (RNNs), our model offers interpretability post-training, alongside reduced complexity and enhanced training efficiency compared to traditional RNNs. Moreover, by leveraging gradient-based optimization, our method surpasses combinatorial approaches in both scalability and noise resilience. Validation experiments conducted on target regular languages of varying size and complexity demonstrate that our approach is accurate, fast, and robust to noise in both the input symbols and the output labels of training data, integrating the strengths of both logical grammar induction and deep learning.