权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Finitie Coalgebras in Minimization and Recursion

最小化和递归中的有限代数

基本信息

批准号：
251268147
负责人：
Professor Dr. Jiri Adámek
金额：
--
依托单位：
Institut für Theoretische Informatik
依托单位国家：
德国
项目类别：
Research Grants
财政年份：
2014
资助国家：
德国
起止时间：
2013-12-31 至 2017-12-31
项目状态：
已结题

来源：
https://gepris.dfg.de/gepris/projekt/251268147?language=en
关键词：
Finitie Coalgebras Minimization Recursion

项目摘要

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.

基于我们最近将终余代数刻画为由全良点余代数构成的余代数的结果，给出了正则语言的“小”非确定自动机的各种构造.这些构造依赖于基范畴的选择，其中自动机被表示为有限余代数。例如，布尔代数范畴产生了Brzozowski和Tamm的a 'tomata，而分配格范畴提供了一个新的构造。在这个项目中，这些不同的构造将被研究和比较，并将制定一个状态最小的非确定自动机的充分条件。有限余代数发挥重要作用的第二个领域是递归。在我们以前的工作中，我们研究了迭代代数，在这个意义上，对于每一个由一个可表示对象携带的余代数，都存在唯一的余代数到代数的同态。在某些应用中，有限可表示性被证明太强，并且必须考虑由可表示生成对象携带的余代数;在其他应用中，只有可表示生成的自由对象起作用。因此，我们计划研究递归的基础上，一个一般的参数，这将使人们有可能选择有限的模型，根据给定的应用程序的需要。