#матлог #учёба #спецсеминар

Kolmogorov seminar on complexity (for receive the zoom link, please email nikolay.vereshchagin@gmail.com)

15 December, 18:30 MSK

Sasha Kozachinskiy

Language identification and generation in the limit.

I will finish my talk about language generation, this time I will present some about language generation for regular and context-free languages.

Annotation of the first part is below.

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.

➰ ВК