SMT-Based Active Learning of Weighted Automata

Tiago Ferreira (✉), Kevin Batz, Alexandra Silva · 2026

Read SMT-Based Active Learning of Weighted Automata by Tiago Ferreira (✉), Kevin Batz, Alexandra Silva (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-07758.txt.

Description

Tiago Ferreira and two co-authors learn weighted automata, using an SMT solver as the engine. Weighted automata assign weights from a semiring to strings, and classic learning algorithms in the Hankel or L-star style are fragile in practice. Their algorithm is built around the semiring and, when it terminates, is certain to return a minimal one.

They prove partial correctness and give a termination condition that covers all finite semirings in particular. In many experiments the learner recovered many minimal machines over finite and infinite semirings. It vastly outperformed a naive baseline. It also stayed competitive with a state-of-the-art algorithm while producing much smaller automata and asking the teacher fewer queries.

Catalog record

CREATORTiago Ferreira (✉), Kevin Batz, Alexandra Silva
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE67 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.07758

Browse the full library · About the Tower of Babel