{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/129223"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/129223","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Learning symbolic concepts and domain-specific languages","abstract":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2025-10-19 without embargo terms","abstract_html":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2025-10-19 without embargo terms","abstract_has_math":false,"creators":["Krogmeier, Paul M"],"institution":"University of Illinois Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Parthasarathy, Madhusudan","Viswanathan, Mahesh","Singh, Gagandeep","Solar-Lezama, Armando"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2025,"date_issued":"2025-04-21","date_published":"2025-04-21","updated_at":"2026-07-22T22:25:04Z","subjects":["symbolic learning","tree automata","programming languages","domain-specific languages","logic","synthesis","axioms"],"languages":["en","eng"],"rights":["Copyright 2025 Paul Krogmeier"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/129223","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Parthasarathy, Madhusudan","Viswanathan, Mahesh","Singh, Gagandeep","Solar-Lezama, Armando"]},{"key":"dc:creator","label":"Author","values":["Krogmeier, Paul M"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2025-04-21","2025-05"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["symbolic learning","tree automata","programming languages","domain-specific languages","logic","synthesis","axioms"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en","eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2025 Paul Krogmeier"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/129223"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2025-10-19 without embargo terms","The student, Paul Krogmeier, accepted the attached license on 2025-04-19 at 10:27.","The student, Paul Krogmeier, submitted this Dissertation for approval on 2025-04-19 at 11:00.","This Dissertation was approved for publication on 2025-04-21 at 11:37.","DSpace SAF Submission Ingestion Package generated from Vireo submission #21846 on 2025-10-19 at 18:09:33","Symbolic concept learning is a fundamental problem with numerous applications in program testing, verification, synthesis, and discovery of mathematical theorems and physical laws. We investigate in this dissertation the decidability of symbolic learning in different formal languages and provide new decision procedures for their learning problems. We develop an algorithm based on tree automata that can decide the existence of logic formulas which correctly classify a given set of labeled structures, where formulas come from fragments of finite-variable first-order logics defined by regular constraints on formula syntax trees. We show that alternating tree automata can evaluate quantified logic formulas over finite structures and use this to give an exponential time upper bound for learning. We prove a matching lower bound. We show also that finite-variable logics with recursion have decidable learning by moving to two-way tree automata which evaluate recursive definitions by traversing syntax trees up and down several times. We also prove decidable learning results for finite-variable second-order logics and Datalog programs. Next we show that these learning algorithms generalize to languages beyond finite-variable logics. We prove a meta-theorem which says that learning in a language L is decidable if we can devise a restricted program P which evaluates expressions of L over fixed structures. Provided that P does not need more and more memory for larger and larger expressions, it can be translated with a learning instance into a tree automaton that accepts exactly the set of solutions; this reduces learning problems to the emptiness problem for these tree automata. We use the meta-theorem to prove new decidable learning results by exhibiting evaluation programs for several languages: modal logic and computation tree logic over finite Kripke structures, linear temporal logic over ultimately periodic words, regular expressions and context-free grammars over finite words, first-order logic queries over rational numbers, and text-manipulation programs for spreadsheet automation. We next turn to the problem of synthesizing domain-specific languages (DSLs) which succinctly express symbolic concepts in specific domains and thereby enable learning from few examples. We formulate novel DSL synthesis problems involving the synthesis of grammars with and without macros, and we prove decidability results for each. Finally, we formulate an axiom synthesis problem in which the goal is to synthesize a set of logic formulas which precisely characterize a target class of mathematical structures. We propose a general learning-based algorithmic framework for solving axiom synthesis and instantiate it to synthesize axiomatizations in modal logic and Kleene algebra."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Learning symbolic concepts and domain-specific languages"]}]}],"canonical_facts":{"dc:contributor":["Parthasarathy, Madhusudan","Viswanathan, Mahesh","Singh, Gagandeep","Solar-Lezama, Armando"],"dc:creator":["Krogmeier, Paul M"],"dc:date":["2025-04-21","2025-05"],"dc:description":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2025-10-19 without embargo terms","The student, Paul Krogmeier, accepted the attached license on 2025-04-19 at 10:27.","The student, Paul Krogmeier, submitted this Dissertation for approval on 2025-04-19 at 11:00.","This Dissertation was approved for publication on 2025-04-21 at 11:37.","DSpace SAF Submission Ingestion Package generated from Vireo submission #21846 on 2025-10-19 at 18:09:33","Symbolic concept learning is a fundamental problem with numerous applications in program testing, verification, synthesis, and discovery of mathematical theorems and physical laws. We investigate in this dissertation the decidability of symbolic learning in different formal languages and provide new decision procedures for their learning problems. We develop an algorithm based on tree automata that can decide the existence of logic formulas which correctly classify a given set of labeled structures, where formulas come from fragments of finite-variable first-order logics defined by regular constraints on formula syntax trees. We show that alternating tree automata can evaluate quantified logic formulas over finite structures and use this to give an exponential time upper bound for learning. We prove a matching lower bound. We show also that finite-variable logics with recursion have decidable learning by moving to two-way tree automata which evaluate recursive definitions by traversing syntax trees up and down several times. We also prove decidable learning results for finite-variable second-order logics and Datalog programs. Next we show that these learning algorithms generalize to languages beyond finite-variable logics. We prove a meta-theorem which says that learning in a language L is decidable if we can devise a restricted program P which evaluates expressions of L over fixed structures. Provided that P does not need more and more memory for larger and larger expressions, it can be translated with a learning instance into a tree automaton that accepts exactly the set of solutions; this reduces learning problems to the emptiness problem for these tree automata. We use the meta-theorem to prove new decidable learning results by exhibiting evaluation programs for several languages: modal logic and computation tree logic over finite Kripke structures, linear temporal logic over ultimately periodic words, regular expressions and context-free grammars over finite words, first-order logic queries over rational numbers, and text-manipulation programs for spreadsheet automation. We next turn to the problem of synthesizing domain-specific languages (DSLs) which succinctly express symbolic concepts in specific domains and thereby enable learning from few examples. We formulate novel DSL synthesis problems involving the synthesis of grammars with and without macros, and we prove decidability results for each. Finally, we formulate an axiom synthesis problem in which the goal is to synthesize a set of logic formulas which precisely characterize a target class of mathematical structures. We propose a general learning-based algorithmic framework for solving axiom synthesis and instantiate it to synthesize axiomatizations in modal logic and Kleene algebra."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/129223"],"dc:language":["en","eng"],"dc:rights":["Copyright 2025 Paul Krogmeier"],"dc:subject":["symbolic learning","tree automata","programming languages","domain-specific languages","logic","synthesis","axioms"],"dc:title":["Learning symbolic concepts and domain-specific languages"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:04Z"}