# Learning Deterministic Finite Automata from Confidence Oracles

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 2 of its 12 references that are in the map.
- First posted on arXiv 18 Nov 2023.

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

- [Extracting Automata from Recurrent Neural Networks Using Queries and Counterexamples](https://mlsanity.com/paper/1711.09576/) (2017)
- [An Empirical Evaluation of Rule Extraction from Recurrent Neural Networks](https://mlsanity.com/paper/1709.10380/) (2017)

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

- [On the Statistical Query Complexity of Learning Semiautomata: a Random Walk Approach](https://mlsanity.com/paper/2510.04115/) (2025)

## Abstract (arXiv)

We discuss the problem of learning a deterministic finite automaton (DFA) from a confidence oracle. That is, we are given access to an oracle Q with incomplete knowledge of some target language L over an alphabet Sigma; the oracle maps a string x∈Sigma^* to a score in the interval [-1,1] indicating its confidence that the string is in the language. The interpretation is that the sign of the score signifies whether x∈ L, while the magnitude |Q(x)| represents the oracle's confidence. Our goal is to learn a DFA representation of the oracle that preserves the information that it is confident in. The learned DFA should closely match the oracle wherever it is highly confident, but it need not do this when the oracle is less sure of itself.