一句话：研究 FDFA 作为 ω-正则语言接受器的复杂度：布尔运算与判定问题可在 NLOGSPACE 完成，并给出与 ω-自动机的翻译及简洁性比较。
DFA 族（FDFA）是识别 ω-正则语言的一种替代形式，其动机是让状态与右同余关系对应，类似 Myhill–Nerode 定理，便于学习算法。本文考察 FDFA 定义 ω-正则语言的适用性：补、交等布尔运算，空性与包含等判定问题的复杂度，以及相较确定/非确定 ω-自动机的简洁性。结果显示，FDFA 在布尔运算与判定问题上具确定自动机优势，均可在非确定对数空间内完成；确定 Büchi/co-Büchi 自动机到 FDFA、FDFA 到非确定 Büchi 自动机（NBA）有多项式翻译，而 NBA 到 FDFA 可能指数膨胀。FDFA 比确定 parity 自动机（DPA）更简洁：DPA 到 FDFA 仅多项式增长，反向最坏情况指数膨胀。
Families of DFAs (FDFAs) provide an alternative formalism for recognizing $\omega$-regular languages. The motivation for introducing them was a desired correlation between the automaton states and right congruence relations, in a manner similar to the Myhill-Nerode theorem for regular languages. This correlation is beneficial for learning algorithms, and indeed it was recently shown that $\omega$-regular languages can be learned from membership and equivalence queries, using FDFAs as the acceptors. In this paper, we look into the question of how suitable FDFAs are for defining omega-regular languages. Specifically, we look into the complexity of performing Boolean operations, such as complementation and intersection, on FDFAs, the complexity of solving decision problems, such as emptiness and language containment, and the succinctness of FDFAs compared to standard deterministic and nondeterministic $\omega$-automata. We show that FDFAs enjoy the benefits of deterministic automata with respect to Boolean operations and decision problems. Namely, they can all be performed in nondeterministic logarithmic space. We provide polynomial translations of deterministic B\"uchi and co-B\"uchi automata to FDFAs and of FDFAs to nondeterministic B\"uchi automata (NBAs). We show that translation of an NBA to an FDFA may involve an exponential blowup. Last, we show that FDFAs are more succinct than deterministic parity automata (DPAs) in the sense that translating a DPA to an FDFA can always be done with only a polynomial increase, yet the other direction involves an inevitable exponential blowup in the worst case.
@article{paperbot426,
title = {Families of DFAs as Acceptors of $\omega$-Regular Languages},
author = {Dana Angluin and Udi Boker and Dana Fisman},
journal = {Logical Methods in Computer Science},
volume = {Volume 14, Issue 1},
year = {2018},
doi = {10.23638/lmcs-14(1:15)2018}
}