Languages with Decidable Learning: A Meta-theorem

Explore a groundbreaking meta-theorem on decidable learning in symbolic languages presented at OOPSLA1 2023. Delve into the concept of finite-aspect checkable languages and their role in characterizing symbolic languages with decidable learning. Discover how the semantics of these languages can be defined using bounded auxiliary information, independent of expression size but dependent on a fixed evaluation structure. Learn about a novel generic programming language for evaluating expression syntax trees and understand its connection to finite tree automata. Examine how this meta-theorem enables the derivation of new decidable learning results and decision procedures for various expression learning problems. Gain insights into exact learning, symbolic language learning, tree automata, version space algebra, program synthesis, and interpretable learning through this 18-minute video presentation by researchers from the University of Illinois at Urbana-Champaign.