[pl-seminar] Tomorrow's talk

[Qinheping HU <qhu28@xxxxxxxx>]

Hi every,

Tomorrow noon at 4310cs Sam will give a practice talk fro the paper Learning Symbolic Automata.

Abstract:

Symbolic automata allow transitions to carry predicates over rich alphabet theories, such as linear arithmetic, and therefore extend classic automata to operate over infinite alphabets, such as the set of rational numbers. In this paper, we study the foundational problem of learning symbolic automata. We first present Îâ , a symbolic automata extension of Angluinâs Lâ algorithm for learning regular languages. Then, we define notions of learnability that are parametric in the alphabet theories of the symbolic automata and show how these notions nicely compose. Specifically, we show that if two alphabet theories are learnable, then the theory accepting the Cartesian product or disjoint union of their alphabets is also learnable. Using these properties, we show how existing algorithms for learning automata over large alphabets nicely fall in our framework.

Best,

Qinheping