论文标题
关于残留自动机的基于Quasiorder的观点
A Quasiorder-based Perspective on Residual Automata
论文作者
论文摘要
在这项工作中，我们定义了一个基于单词的准构件的自动机构构造框架，以提供有关残留自动机的类别的新见解。我们提出了一种新的残差操作和一种通用的双反转方法，用于为给定语言构建规范残差自动机。最后，我们使用框架为NL*提供了基于Quasiorder的视角，NL*是一种用于剩余自动机的在线学习算法。我们得出的结论是，由于确定性自动机的一致性，准自动机是剩余自动机的基础。
In this work, we define a framework of automata constructions based on quasiorders over words to provide new insights on the class of residual automata. We present a new residualization operation and a generalized double-reversal method for building the canonical residual automaton for a given language. Finally, we use our framework to offer a quasiorder-based perspective on NL*, an online learning algorithm for residual automata. We conclude that quasiorders are fundamental to residual automata as congruences are to deterministic automata.
