2024/09/17 by Kevin Zhou, Zhou, Kevin
Computer Science · #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Machine Learning and Algorithms #Optimization and Search Problems #Software Testing and Debugging Techniques
paper · pdf · doi:10.48550/arxiv.2409.10822
openalex publication_date 2024/09/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Learning automata by queries is a long-studied area initiated by Angluin in 1987 with the introduction of the L^* algorithm to learn regular languages, with a large body of work afterwards on many different variations and generalizations of DFAs. Recently, Chase and Freitag introduced a novel approach to proving query learning bounds by computing combinatorial complexity measures for the classes in question, which they applied to the setting of DFAs to obtain qualitatively different results compared to the L^* algorithm. Using this approach, we prove new query learning bounds for two generalizations of DFAs. The first setting is that of advice DFAs, which are DFAs augmented with an advice string that informs the DFA's transition behavior at each step. For advice DFAs, we give the first known upper bounds for query complexity. The second setting is that of nominal DFAs, which generalize DFAs to infinite alphabets which admit some structure via symmetries. For nominal DFAs, we make qualitative improvements over prior results.