Result: Active Learning of Upward-Closed Sets of Words
Title:
Active Learning of Upward-Closed Sets of Words
Authors:
Contributors:
Aristote, Quentin
Publication Status:
Preprint
Publisher Information:
arXiv, 2025.
Publication Year:
2025
Subject Terms:
FOS: Computer and information sciences, well quasi-orders, Formal Languages and Automata Theory (cs.FL), active learning, F.4.3, piecewise-testable languages, monoids, Valk-Jantzen lemma, Formal Languages and Automata Theory, [INFO.INFO-FL] Computer Science [cs]/Formal Languages and Automata Theory [cs.FL]
Document Type:
Academic journal
Article<br />Conference object
File Description:
application/pdf
DOI:
10.48550/arxiv.2504.21429
DOI:
10.4230/lipics.calco.2025.16
Access URL:
Rights:
CC BY
Accession Number:
edsair.doi.dedup.....16b7ed14dccbb3b1b5a40d9525537f80
Database:
OpenAIRE
Further Information
We give a new proof of a result from well quasi-order theory on the computability of bases for upwards-closed sets of words. This new proof is based on Angluin's L* algorithm, that learns an automaton from a minimally adequate teacher. This relates in particular two results from the 1980s: Angluin's L* algorithm, and a result from Valk and Jantzen on the computability of bases for upwards-closed sets of tuples of integers. Along the way, we describe an algorithm for learning quasi-ordered automata from a minimally adequate teacher, and extend a generalization of Valk and Jantzen's result, encompassing both words and integers, to finitely generated monoids.
13 pages, 2 figures; presented at CALCO 2025