2023/07/14 by Yong Li, Sven Schewe, Li, Yong +3 · 1 citation
Computer Science · Engineering · #FOS: Computer and information sciences #Ferroelectric and Negative Capacitance Devices #Formal Languages and Automata Theory (cs.FL) #Machine Learning and Algorithms #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2307.07490
openalex publication_date 2023/07/14 · openalex created_date 2023/07/18 · openalex updated_date 2026/07/28
Families of DFAs (FDFAs) have recently been introduced as a new representation of ω-regular languages. They target ultimately periodic words, with acceptors revolving around accepting some representation u⋅ vω. Three canonical FDFAs have been suggested, called periodic, syntactic, and recurrent. We propose a fourth one, limit FDFAs, which can be exponentially coarser than periodic FDFAs and are more succinct than syntactic FDFAs, while they are incomparable (and dual to) recurrent FDFAs. We show that limit FDFAs can be easily used to check not only whether ω-languages are regular, but also whether they are accepted by deterministic Büchi automata. We also show that canonical forms can be left behind in applications: the limit and recurrent FDFAs can complement each other nicely, and it may be a good way forward to use a combination of both. Using this observation as a starting point, we explore making more efficient use of Myhill-Nerode's right congruences in aggressively increasing the number of don't-care cases in order to obtain smaller progress automata. In pursuit of this goal, we gain succinctness, but pay a high price by losing constructiveness.