Finitie Coalgebras in Minimization and Recursion

基于我们最近将终端余代数刻画为由全好点余代数组成的余代数，得到了给定正则语言的“小”不确定自动机的各种构造。这些构造依赖于自动机被表示为有限余代数的基范畴的选择。例如，布尔代数范畴产生Brzozowski和Tamm的a‘tomata，而分配格范畴提供了一种新的结构。在这个项目中，将研究和比较这些不同的结构，并将建立找到状态最小非确定自动机的充分条件。有限余代数发挥重要作用的第二个领域是递归。在我们以前的工作中，我们研究了迭代代数，即对于有限可表示对象承载的每个余代数，存在唯一的余代数到代数同态。在某些应用中，有限可表示性被证明是太强的，并且必须考虑由有限生成对象承载的余代数；在其他应用中，仅有限生成的自由对象起作用。因此，我们计划研究基于一般参数的递归，以便能够根据特定应用的需要来选择有限模型。

Based on our recent characterization of terminal coalgebras as coalgebras consisting of allwell-pointed coalgebras, various constructions of "small" nondeterministic automatafor a given regular language are obtained. These constructions depend on the choice of thebase category where automata are presented as finite coalgebras. For example the category ofboolean algebras yields the a'tomata of Brzozowski and Tamm, whereas the categoryof distributive lattices provides a new construction. In the project these various constructionswill be studied and compared, and sufficient conditions for finding a state-minimal non-deterministicautomaton will be formulated.A second realm where finite coalgebras play a significant role is recursion. In our previouswork we studied algebras that are iterative in the sense that for every coalgebra carried bya finitely presentable object a unique coalgebra-to-algebra homomorphisms exists.In some applications finite presentability turned out to be too strong, and coalgebrascarried by finitely generated objects had to be considered; in other applications just thefinitely generated free objects played a role. We therefore plan to study recursion based ona general parameter that would make it possible to choose the model of finiteness according to the needs of the given application.