EVENT

Event News

MTSS Center Colloquium by Kevin Zhou

On Tuesday 26 August, Kevin Zhou (National Institute of Informatics) will give a talk, "Query learning bounds for advice and nominal automata", for our colloquium at 16:30. Further details can be found below.

Title:

Query learning bounds for advice and nominal automata

Abstract:

In the setting of query learning, one attempts to learn an unknown target function by asking queries to an oracle in an interactive fashion. This setting is well-suited for learning the behavior of real-world systems modeled by automata, since queries can often be simulated by interacting with the system. The area of learning automata by queries has a long history dating back to 1987, when Angluin introduced the L* algorithm which learns regular languages. Since then, much work has been done adapting the L* algorithm to other forms of automata.

More recently, Chase and Freitag introduced a general framework for obtaining query learning bounds, which yields qualitatively different results from Angluin's original approach. Their technique involves bounding the number of queries needed in terms of various combinatorial notions of dimension, a common theme in computational learning theory. We apply this technique to two types of automata: advice DFAs and nominal DFAs. Advice DFAs augment classical DFAs with an advice string which informs the DFA's transition behavior at each step, while nominal DFAs generalize DFAs to suitably well-behaved infinite alphabets. For advice DFAs, we give the first known upper bounds for query complexity, while for nominal DFAs, we make qualitative improvements over prior results.