# An L^* Algorithm for Deterministic Weighted Regular Languages

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 27 references that are in the map.
- First posted on arXiv 9 Nov 2024.

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

- [Extracting Automata from Recurrent Neural Networks Using Queries and Counterexamples](https://mlsanity.com/paper/1711.09576/) (2017)
- [Sequential Neural Networks as Automata](https://mlsanity.com/paper/1906.01615/) (2019)
- [On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoning](https://mlsanity.com/paper/2406.14197/) (2024)
- [Learning Deterministic Weighted Automata with Queries and Counterexamples](https://mlsanity.com/paper/1910.13895/) (2019)
- [Weighted Automata Extraction from Recurrent Neural Networks via Regression on State Spaces](https://mlsanity.com/paper/1904.02931/) (2019)
- [Transparency at the Source: Evaluating and Interpreting Language Models With Access to the True Distribution](https://mlsanity.com/paper/2310.14840/) (2023)

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

- [SMT-Based Active Learning of Weighted Automata](https://mlsanity.com/paper/2605.07758/) (2026)

## Abstract (arXiv)

Extracting finite state automata (FSAs) from black-box models offers a powerful approach to gaining interpretable insights into complex model behaviors. To support this pursuit, we present a weighted variant of Angluin's (1987) L^* algorithm for learning FSAs. We stay faithful to the original algorithm, devising a way to exactly learn deterministic weighted FSAs whose weights support division. Furthermore, we formulate the learning process in a manner that highlights the connection with FSA minimization, showing how L^* directly learns a minimal automaton for the target language.