Languages with Decidable Learning: A Meta-theorem
summary
Proves a concrete meta-theorem: if a symbolic language admits a facet interpreter whose extra memory is bounded by the fixed structure (independent of expression size), that interpreter compiles to two-way alternating tree automata and learning reduces to automaton emptiness. Implements translations and derives decision procedures for seven cases (regular expressions, context-free grammars, Flash Fill DSL functions, LTL/CTL/modal logics, FO over rationals). The toolchain is formalized and correct by construction; complexity and practical scaling remain open but the decision procedures are proven to work.
AI-written summary · about
chapters (8)
- 0:00Decidable learning in symbolic languages
- 1:26Symbolic learning from examples
- 4:15Meta-theorem for learning algorithms
- 7:01Compiling interpreters to decision procedures
- 10:10Languages with decidable learning
- 12:57Future directions and open questions
- 14:22Summary and applications
- 15:09Question and answer session
related talks
15mSynthesizing DSLs for Few-Shot Learning
25mLearning Formulas in Finite Variable Logics
50mA Type-Theoretic Framework for Certified Meta-programming
01h 07mBack to the Future: A Fresh Look at Linear Temporal Logic
45mLogic Meta Programming for Functional Languages
18mOn the Expressive Power of Languages for Static Variability
31mLetting users do the undecidable: lessons from program synthesis
09mRetargeting an Abstract Interpreter for a New Language by Partial Evaluation (Short Paper)