An $\mathbf{L^*}$ Algorithm for Deterministic Weighted Regular Languages

Clemente Pasti, Talu Karagöz, Anej Svete, Franz Nowak, Reda Boumasmoud +1 more
11/9/2024
cs.CL

No confident code implementation found for this paper.

Abstract

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) $\mathbf{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 $\mathbf{L^*}$ directly learns a minimal automaton for the target language.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

$L^*LM$: Learning Automata from Examples using Natural Language Oracles

83% match2024

Active Learning of Symbolic Automata Over Rational Numbers

83% match2025

Learning Weighted Finite Automata over the Max-Plus Semiring and its Termination

82% match2024

Unsupervised Automata Learning via Discrete Optimization

79% match2023

Beyond Memorization: Testing LLM Reasoning on Unseen Theory of Computation Tasks

79% match2026

DeepDFA: Automata Learning through Neural Probabilistic Relaxations

78% match1 repo82024

Cite this paper

@article{pasti2024mathbfl,
  title  = {An $\mathbf{L^*}$ Algorithm for Deterministic Weighted Regular Languages},
  author = {Clemente Pasti and Talu Karagöz and Anej Svete and Franz Nowak and Reda Boumasmoud and Ryan Cotterell},
  year   = {2024},
  eprint = {2411.06228},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2411.06228v2}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2411.06228.svg)](https://codeofpaper.com/paper/2411.06228)

Discussion