Исследовательская группа

Лаборатория языковых инструментов

Learning Formulas in Finite Variable Logics (POPL'22)

7 марта

We consider grammar-restricted exact learning of formulas and terms in finite variable logics. We propose a novel and versatile automata-theoretic technique for solving such problems. We first show results for learning formulas that classify a set of positively- and negatively-labeled structures. We give algorithms for realizability and synthesis of such formulas along with upper and lower bounds. We also establish positive results using our technique for other logics and variants of the learning problem, including first-order logic with least fixed point definitions, higher-order logics, and synthesis of queries and terms with recursively-defined functions.

Speaker: Paul Krogmeier (PhD student at University of Illinois at Urbana-Champaign, USA)

Paper: https://dl.acm.org/doi/abs/10.1145/3498671

Google Meet: https://meet.google.com/myu-dhmz-gvu