On well-founded and recursive coalgebras

DOI10.1007/978-3-030-45231-5_2MaRDI QIDQ2200809zbMATH OpenOpenAlexFDO

Authors Jiří Adámek, Stefan Milius, Lawrence S. Moss

Publication date 23 September 2020

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1910.09401

zbMATH Keywords

initial algebrageneral recursion theoremwell-founded recursive coalgebra

Mathematics Subject Classification ID

Categorical semantics of formal languages (18C50) Abstract data types; algebraic specification (68Q65) Foundations, relations to logic and deductive systems (18A15)

Abstract: This paper studies fundamental questions concerning category-theoretic models of induction and recursion. We are concerned with the relationship between well-founded and recursive coalgebras for an endofunctor. For monomorphism preserving endofunctors on complete and well-powered categories every coalgebra has a well-founded part, and we provide a new, shorter proof that this is the coreflection in the category of all well-founded coalgebras. We present a new more general proof of Taylor's General Recursion Theorem that every well-founded coalgebra is recursive, and we study under which hypothesis the converse holds. In addition, we present a new equivalent characterization of well-foundedness: a coalgebra is well-founded iff it admits a coalgebra-to-algebra morphism to the initial algebra.

Recommendations

• Recursive coalgebras from comonads
• Recursive coalgebras of finitary functors
• Well-founded coalgebras, revisited
• Terminal coalgebras in well-founded set theory
• Recursive coalgebras from comonads

Cites work

• scientific article; zbMATH DE number 42752 (Why is no real title available?)
• A theory of bisimulation for the \(\pi\)-calculus
• An algebra of quantum processes
• Automated equivalence checking of concurrent quantum systems
• Bisimulation for quantum processes
• Communicating quantum processes
• Deciding bisimilarity and similarity for probabilistic processes.
• Open bisimulation for quantum processes
• Polynomial time decision algorithms for probabilistic automata
• Probabilistic bisimulations for quantum processes
• Quantum cryptography: public key distribution and coin tossing
• Relations among quantum processes: bisimilarity and congruence
• Semi-automated verification of security proofs of quantum cryptographic protocols
• Symbolic bisimulation for quantum processes
• Symbolic bisimulations
• Towards a quantum programming language

Cited in

(13)

• Recursive coalgebras from comonads
• Recursive coalgebras from comonads
• The Recursion Scheme from the Cofree Recursive Comonad
• Well-pointed coalgebras (extended abstract)
• On the foundations of final coalgebra semantics: non-well-founded sets, partial orders, metric spaces
• Well-founded coalgebras, revisited
• Additions and corrections to ``Terminal coalgebras in well-founded set theory
• A categorical framework for learning generalised tree automata
• Corecursive algebras in nature
• Cofree coalgebras and multivariable recursiveness.
• Recursive coalgebras of finitary functors
• Categorical liveness checking by corecursive algebras
• Well-pointed coalgebras

This page was built for publication: On well-founded and recursive coalgebras

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2200809)