Learning Formulas in Finite Variable Logics
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.
Fri 21 JanDisplayed time zone: Eastern Time (US & Canada) change
16:40 - 17:30
|Learning Formulas in Finite Variable LogicsDistinguished PaperInPerson|
Paul Krogmeier University of Illinois at Urbana-Champaign, P. Madhusudan University of Illinois at Urbana-ChampaignDOI Media Attached
|Bottom-Up Synthesis of Recursive Functional Programs using Angelic ExecutionDistinguished PaperRemote|
Anders Miltner University of Texas at Austin, Adrian Trejo Nuñez University of Texas at Austin, Ana Brendel University of Texas at Austin, Swarat Chaudhuri University of Texas at Austin, Işıl Dillig University of Texas at AustinDOI Media Attached