Learning formulas in finite variable logics

Paul Krogmeier, P. Madhusudan

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Article number3498671
JournalProceedings of the ACM on Programming Languages
Issue numberPOPL
StatePublished - Jan 2022


  • exact learning
  • interpretable learning
  • learning formulas
  • program synthesis
  • tree automata
  • version space algebra

ASJC Scopus subject areas

  • Software
  • Safety, Risk, Reliability and Quality

Cite this