Computer Science Theory Seminar
Kevin Zhou
UIC
Query Learning of Automata
Abstract: Query learning of automata is a well-studied area of problems, beginning with work of Angluin in 1987 introducing the L* algorithm for DFAs, with a large body of ensuing work applying Angluin's approach to variants and generalizations of DFAs. Most results in the area utilize Angluin's basic method, tailoring the details of the algorithms on a case-by-case basis. Recent work by Chase and Freitag took an alternative approach inspired by model theory, proving general bounds for query learning in terms of various combinatorial measures of complexity. Applying this approach to the setting of DFAs, they obtain new learnability results of a qualitatively different flavor than those of Angluin. We extend these results, proving new bounds in the query complexity of two generalizations of finite automata - automata with advice and nominal automata.
Wednesday December 1, 2021 at 4:00 PM in 636 SEO