论文标题
关于最小化和学习确定性$ω$ -AUTOMATA在不在乎单词的情况下
On Minimization and Learning of Deterministic $ω$-Automata in the Presence of Don't Care Words
论文作者
论文摘要
我们研究确定性$ω$ -Automata的最小化问题，在不在乎言语的情况下。我们证明，确定性平价自动机的优先级数量可以在任意的一组不在乎单词的情况下有效地最小化。我们得出的是，从更一般的结果中，从中也获得了有效的最小化算法的确定性平价自动机，并提供了信息丰富的右派（不关心单词）。 然后，我们分析不关心用右键的语言来分析语言。对于这组不在乎单词，众所周知，弱确定性的Büchi自动机（WDBA）具有独特的最小自动机，可以从给定的WDBA有效地计算出来（Eisinger，Klaedtke，2006）。我们对相应的最小WDBA进行了基于一致的表征，并表明WDBA的最小化结果并没有扩展到确定性的$ω$ -Automata，并且提供信息丰富的右键：对于此类班级，没有独特的最小自动机，因为给定的不在乎的是与琐碎的正确的祝贺，并且是np-yimimimation n n pp-Hard。最后，我们将WDBA的积极学习算法（Maler，Pnueli 1995）扩展到了设置，并用一组额外的不在乎右键的不关心单词。
We study minimization problems for deterministic $ω$-automata in the presence of don't care words. We prove that the number of priorities in deterministic parity automata can be efficiently minimized under an arbitrary set of don't care words. We derive that from a more general result from which one also obtains an efficient minimization algorithm for deterministic parity automata with informative right-congruence (without don't care words). We then analyze languages of don't care words with a trivial right-congruence. For such sets of don't care words it is known that weak deterministic Büchi automata (WDBA) have a unique minimal automaton that can be efficiently computed from a given WDBA (Eisinger, Klaedtke 2006). We give a congruence-based characterization of the corresponding minimal WDBA, and show that the don't care minimization results for WDBA do not extend to deterministic $ω$-automata with informative right-congruence: for this class there is no unique minimal automaton for a given don't care set with trivial right congruence, and the minimization problem is NP-hard. Finally, we extend an active learning algorithm for WDBA (Maler, Pnueli 1995) to the setting with an additional set of don't care words with trivial right-congruence.
