Learning Formulas in Finite Variable Logics

We investigate exact learning of formulas in finite-variable logics over positively- and negatively-labeled finite structures. We propose a general automata-theoretic solution, establish decidability, and give algorithms for synthesis. We also study variants of the learning problem for learning queries and terms, and we provide algorithms for realizability and synthesis along with upper and lower bounds. We study the problem also along the dimension of logics, establishing positive results for first-order logic with least fixed points and several other logics.