Active Learning of Upward-Closed Sets of Words

2025/04/30 by Aristote, Quentin
#F.4.3 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)

paper · doi:10.48550/arxiv.2504.21429

Abstract

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.

Citations

• Active Learning of Deterministic Transducers with Outputs in Arbitrary Monoids
• Learning automata and transducers: a categorical approach
• Learning Weighted Automata over Principal Ideal Domains
• Automata Learning: An Algebraic Approach
• The Ideal Approach to Computing Closed Subsets in Well-Quasi-Ordering
• CALF: Categorical Automata Learning Framework
• Automata theory in nominal sets
• Forward analysis for WSTS, Part I: Completions

Related

• Active Learning for Deterministic Bottom-up Nominal Tree Automata
• Learning automata and transducers: a categorical approach
• Computing downward closures for stacked counter automata
• Feasability of Learning Weighted Automata on a Semiring
• An approach to computing downward closures