Reproduce “Towards a Higher-Order Bialgebraic Denotational Semantics” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Sergey Goncharov, Marco Peressotti, Stelios Tsampas, Henning Urbat, Stefano Volpe

A theory for higher-order bialgebraic denotational semantics introduces locally final coalgebras and M-categories to construct compositional and adequate denotational models. This framework addresses the categorical challenge of non-existent global final higher-order coalgebras, providing a principled foundation for languages including the λ-calculus.

Key insights

  • While global final higher-order coalgebras generally do not exist for typical behavior bifunctors, locally final coalgebras can exist and serve as valid abstract domains for higher-order behaviors.
  • The property of "relative flatness" for higher-order GSOS laws is key to constructing a compatible algebra structure on locally final coalgebras, ensuring compositionality.
  • M-categories, with their metric-space enrichment and fixed-point theorems, provide the necessary mathematical tools to rigorously prove the existence and uniqueness of these locally final coalgebras.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.