一句话：用函子与伴随刻画自动机及其最小化，统一确定化、最小化与句法代数。
论文将语言及其接受器（确定/加权自动机、转换器、幺半群等）视为从规定语言与机器类型的输入范畴到规定输出类型的输出范畴的函子。作者给出输出范畴上的充分条件，以保证相应自动机的最小化存在；并说明如何把输出值范畴之间的伴随提升为自动机范畴之间的伴随。该框架可实例化以统一自动机理论中的若干现象，包括确定化、最小化和句法代数，并在该设定下解释子序列转换器的 Choffrut 最小化算法以及 Brzozowski 最小化算法。
In this paper we regard languages and their acceptors - such as deterministic or weighted automata, transducers, or monoids - as functors from input categories that specify the type of the languages and of the machines to categories that specify the type of outputs. Our results are as follows: A) We provide sufficient conditions on the output category so that minimization of the corresponding automata is guaranteed. B) We show how to lift adjunctions between the categories for output values to adjunctions between categories of automata. C) We show how this framework can be instantiated to unify several phenomena in automata theory, starting with determinization, minimization and syntactic algebras. We provide explanations of Choffrut's minimization algorithm for subsequential transducers and of Brzozowski's minimization algorithm in this setting.Comment: journal version of the CALCO 2017 paper arXiv:1711.03063
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@article{ColcombetP19,
title = {Automata Minimization: a Functorial Approach},
author = {Thomas Colcombet and Daniela Petrişan},
journal = {Logical Methods in Computer Science},
volume = {Volume 16, Issue 1},
year = {2020},
doi = {10.23638/lmcs-16(1:32)2020}
}