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.

基于我们最近将终端岩体作为由Allwell-Point calgebras组成的山地的表征，获得了“小”非确定性自动机的各种结构，以给定的常规语言。这些构造取决于将自动机作为有限结膜出现的基本类别的选择。例如，Boolean代数的类别产生了Brzozowski和Tamm的A'Tomata，而分配晶格类别则提供了新的结构。在该项目中，将研究和比较这些各种构造，并且将制定找到州最小的非确定性Automaton的足够条件。有限的煤层发挥重要作用的第二个领域是递归。在以前的工作中，我们研究了迭代性的代数，从某种意义上说，对于有限呈现的对象，每个携带的山地都存在一个独特的煤层到代数同构的同构。在某些应用中，有限的存在性过于强，并且必须被有限生成的物体造成的煤层；在其他应用中，仅限生成的免费对象起着作用。因此，我们计划研究基于一般参数的递归，这将使根据给定应用的需求选择有限的模型成为可能。