talk 8 december

[kozmath]

Dear participants of the Kolmogorov seminar,

Our next talk is by Sasha Kozachinskiy:

8 December, 18:30 MSK, 16:30 Paris, 
Zoom:
https://u-bordeaux-fr.zoom.us/j/88402787361?pwd=WktCdEhBT3pXN0pLUGg4Z3RuMlpsQT09

Language identification and generation in the limit.

Assume we have a family of formal languages F. An adversary selects a language L from F and starts enumerating elements of L in some order. Our task is to guess L after seeing finitely many elements of the enumeration. If there is an algorithm that does it regardless of the adversary's actions, we call F identifiable in the limit. Angluin (1980) have obtained necessary and sufficient conditions for countable families to be identifiable in the limit and gave an example of the family of ``pattern languages'', satisfying these conditions.

Kleinberg and Mullainathan have recently considered a variation of this setting, where the task is not to guess L but to indicate an infinite subset of L after finitely many steps. Families, for which this is possible, are called generatable in the limit. They have shown that any countable family is generatable in the limit. Moreover, it can be done computably whenever membership query for the family is decidable. In the talk I will cover these results.

Best,
Sasha