Active learning of upward-closed sets of words

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.

Categories