Finitie Coalgebras in Minimization and Recursion

• Applicant: Professor Dr. Jiri Adámek
• Subject Area: Theoretical Computer Science
• Term: from 2014 to 2018
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 251268147

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.

• DFG Programme: Research Grants