Quentin Aristote - Active Learning of Deterministic Transducers with Outputs in Arbitrary Monoids

lmcs:14392 - Logical Methods in Computer Science, October 9, 2025, Volume 21, Issue 4 - https://doi.org/10.46298/lmcs-21(4:7)2025
Active Learning of Deterministic Transducers with Outputs in Arbitrary MonoidsArticle

Authors: Quentin Aristote

We study monoidal transducers, transition systems arising as deterministic automata whose transitions also produce outputs in an arbitrary monoid, for instance allowing outputs to commute or to cancel out. We use the categorical framework for minimization and learning of Colcombet, Petrişan and Stabile to recover the notion of minimal transducer recognizing a language, and give necessary and sufficient conditions on the output monoid for this minimal transducer to exist and be unique (up to isomorphism). The categorical framework then provides an abstract algorithm for learning it using membership and equivalence queries, and we discuss practical aspects of this algorithm's implementation.


Volume: Volume 21, Issue 4
Secondary volumes: Selected Papers of the 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)
Published on: October 9, 2025
Accepted on: June 30, 2025
Submitted on: October 3, 2024
Keywords: Formal Languages and Automata Theory

Consultation statistics

This page has been seen 926 times.
This article's PDF has been downloaded 687 times.