High-level signatures and initial semantics

Benedikt Ahrens, Andre Hirschowitz, Ambroise Lafont, Marco Maggesi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (Scopus)
59 Downloads (Pure)


We present a device for specifying and reasoning about syntax for datatypes, programming languages, and logic calculi. More precisely, we consider a general notion of ‘signature’ for specifying syntactic constructions. Our signatures subsume classical algebraic signatures (i.e., signatures for languages with variable binding, such as the pure lambda calculus) and extend to much more general examples. In the spirit of Initial Semantics, we define the ’syntax generated by a signature’ to be the initial object –if it exists– in a suitable category of models. Our notions of signature and syntax are suited for compositionality and provide, beyond the desired algebra of terms, a well-behaved substitution and the associated inductive/recursive principles. Our signatures are ‘general’ in the sense that the existence of syntax is not automatically guaranteed. In this work, we identify a large class of signatures wich do generate a syntax. This paper builds upon ideas from a previous attempt by Hirschowitz- Maggesi (FICS 2012), which, in turn, was directly inspired by some earlier work of Ghani-Uustalu and Matthes-Uustalu. The main results presented in the paper are computer-checked within the UniMath system.
Original languageEnglish
Title of host publication27th EACSL Annual Conference on Computer Science Logic 2018 (CSL 2018)
EditorsDan R. Ghica, Achim Jung
PublisherSchloss Dagstuhl
Pages4:1 - 4:22
Number of pages22
ISBN (Electronic)978-3-95977-088-0
Publication statusPublished - 21 Aug 2018
Event27th EACSL Annual Conference on Computer Science Logic 2018 (CSL 2018) - Birmingham, United Kingdom
Duration: 4 Sept 20187 Sept 2018

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
PublisherDagstuhl Publishing
ISSN (Electronic)1868-8969


Conference27th EACSL Annual Conference on Computer Science Logic 2018 (CSL 2018)
Country/TerritoryUnited Kingdom


  • initial semantics
  • signatures
  • syntax
  • monadic subsitution
  • computer-checked proofs


Dive into the research topics of 'High-level signatures and initial semantics'. Together they form a unique fingerprint.

Cite this