Model Theory and AI: Results in Query Learning of Automata and Weighted Model Counting

In this thesis, we study two connections between model theory and AI, in the areas of query learning of automata and weighted model counting. Query learning of automata is an line of study with a long history, beginning in 1987 with the introduction of Angluin's L* algorithm that learns DFAs using equivalence and membership queries. This approach has been adapted to many other settings of automata since then. Recently, Chase and Freitag introduced an alternative method for obtaining query learning bounds by proving a characterization of query learnability by the Littlestone and consistency dimensions. We apply this method to two variants of DFAs, namely, advice DFAs and nominal DFAs. In the setting of advice DFAs, we obtain the first known query learning results, and in the setting of nominal DFAs, we obtain qualitative improvements over prior results. Weighted model counting is a problem with connections to statistical relational learning and probabilistic inference. In weighted model counting, the goal is to find, given a method of assigning weights to structures, the weighted count of all models of a first-order theory on a given domain. Most work in this area has focused on finding fragments of first-order logic for which the weighted model count can be computed efficiently. A related problem of studying the unweighted model count for universal theories has been extensively studied in combinatorics, where the goal is to understand the asymptotic growth rates of the number of structures in a hereditary property. Work in this area has often focused on proving classification results that characterize the possible asymptotic growth rates. We study the interactions between these two problems, seeing how structural results for hereditary properties can yield weighted model counting results, and how efficiency results for certain fragments of first-order logic can lead to stronger results in unweighted model counting.