Alternating finite automata through the lens of quasiorders: canonical representation and Angluin-style learning

The property of possessing a canonical representation is fundamental for any class of automata. While deterministic, non-deterministic, and universal automata have well-established canonical representations, the question remains open for alternating automata. In this study, we propose a definition of canonicity for this class of automata and elucidate several of its properties. Furthermore, we present an algorithm for learning the canonical alternating automata for a given language. This algorithm is a novel adaptation of Angluin's renowned L* algorithm, originally designed for learning canonical deterministic automata. Our work contributes to the theoretical understanding of alternating automata and provides a practical approach to their canonical representation, potentially opening new avenues for research in automata theory and formal language learning.