Fibrational Perspectives on Determinization of Finite-State Automata
Thea Li
Colcombet和Petrişan认为,自动机可以从函授的角度进行有用的考虑,将基于函子的“V-automaton”的一般概念引入V。 这使他们能够通过适当选择V来恢复不同的自动机标准概念,他们使用Set和Rel之间的Kleisli辅助进一步分析了Rel-automata的确定性。 在本文中,我们从纤维化的角度重新审视了Colcombet和Petrişan的分析,以Melliès和Zeilberger最近对分类自动机的替代但相关的定义为基础,作为满足有限纤维和独特提升因子特性的函子。 在这样做的过程中,我们从三个方面提高了对决定化的理解:首先,我们仔细描述了确定性在向后模拟方面的普遍性质。 其次,我们使用SpanSet和Rel之间的本地连接来推广Rel自动机的确定性化过程,这为我们提供了规范的向前模拟。 最后,我们还提出了基于保留路径的多集相对加分的替代确定性,我们利用这一点来提供规范的向后模拟。
Colcombet and Petrişan argued that automata may be usefully considered from a functorial perspective, introducing a general notion of "V-automaton" based on functors into V. This enables them to recover different standard notions of automata by choosing V appropriately, and they further analyzed the determinization for Rel-automata using the Kleisli adjunction between Set and Rel. In this paper, we revisit Colcombet and Petrişan's analysis from a fibrational perspective, building on Melliès and ...
