Invitation to the Logic Seminar at the National University of Singapore
Date: Wednesday, 21 January 2015, 17:00 hrs
Room: S17#05-11, Department of Mathematics, NUS
Speaker: Sanjay Jain.
Title: Parallel learning of automatic classes of languages.
We introduce and explore a model for parallel learning of families of
languages computable by finite automata. In this model, an algorithmic or
automatic learner takes on n different input languages and
identifies at least m of them correctly. For finite parallel learning,
for large enough families, we establish a full characterization
of learnability in terms of characteristic samples of languages. Based on
this characterization, we show that it is the difference n-m,
the number of languages which are potentially not identified, which is
crucial. Similar results are obtained also for parallel learning in the
limit. We consider also parallel finite learnability by finite automata
and obtain some partial results.
This is joint work with Efim Kinber