Sanjay Jain: Parallel learning of automatic classes of languages

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

Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload CAPTCHA.