Logic Seminar
Kevin H Zhou
UIC
Query learning of automat
Abstract: Learning automata by queries is a long-studied area of problems with many applications in AI, automatic verification, model checking, and more. In this setting, a learner plays a game with an oracle, where the goal is to identify some unknown target automaton by interactively submitting queries to the oracle. The study of query learning of automata was initiated by Angluin in 1987 with the introduction of the L* algorithm that learns deterministic finite automata (DFAs) with a polynomial number of queries, and most subsequent work has focused on adapting the L* algorithm to different settings. More recently, Chase and Freitag used ideas from model theory to develop query learning bounds in terms of the Littlestone and consistency dimensions, and apply this to the setting of regular languages to obtain qualitatively different results compared to Angluin. We extend this work, applying the method to two generalizations of DFAs: 1) advice DFAs, where the automaton has access to a fixed advice string, and 2) nominal DFAs, a generalization of DFAs to infinite alphabets and state sets. In the setting of advice DFAs, we obtain the first known query learning results, while in the setting of nominal DFAs, we obtain significant improvements over prior work.
Tuesday October 25, 2022 at 4:00 PM in 636 SEO