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.