Семинары: N. A. Bazhenov, Learning for families of algebraic structures

СЕМИНАРЫ


Семинары отдела математической логики "Теория доказательств" и "Logic Online Seminar" 4 апреля 2023 г. 18:30, г. Москва, МИАН, комн. 110 (ул. Губкина, 8) + Zoom

Learning for families of algebraic structures N. A. Bazhenov Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk
Аннотация: A learner is a function $M$ which, given a finite amount of data about a countable algebraic structure $S$, outputs a conjecture about the isomorphism type of the input structure. A family of structures $K$ is learnable if there exists a learner which for any $S$ from $K$, given larger and larger amounts of $S$-data, eventually correctly identifies the isomorphism type of $S$. In the talk, we discuss two characterizations of learnability: the first one uses the syntax of infinitary logic $L_{\omega_1, \omega}$, and the second one connects learnability with the benchmark combinatorial Borel equivalence relations. Язык доклада: английский