Automata Learning with an Incomplete but Inductive Teacher

Daniel Stan, Adrien Pommellet, Juliette Jacquot · 2026

Read Automata Learning with an Incomplete but Inductive Teacher by Daniel Stan, Adrien Pommellet, Juliette Jacquot (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-2602-21073.txt.

Description

Active automata learning usually assumes a teacher who answers every query fully. Daniel Stan, Adrien Pommellet, and Juliette Jacquot relax that assumption in this 2026 arXiv technical report. Their IdMAT teacher answers with respect to any language in a target class at once, which suits problems like language separation and invariant synthesis that admit many correct answers.

Such a teacher may answer don't know, yet also supply inductive facts of the form: if one word is accepted, so is another. The companion algorithm LIndA encodes all uncertainty as a single SAT instance without forking, uses incremental solving with unsatisfiable-core analysis, and handles both kinds of counterexamples frugally. A prototype is evaluated on language separation and regular model checking.

Catalog record

CREATORDaniel Stan, Adrien Pommellet, Juliette Jacquot
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE66 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-21073

Browse the full library · About the Tower of Babel