Abstract: We give a new general definition of arity, yielding the companion notions of signature and associated syntax. This setting is modular in the sense requested by [12]: merging two extensions of syntax corresponds to building an amalgamated sum. These signatures are too general in the sense that we are not able to prove the existence of an associated syntax in this general context. So we have to select arities and signatures for which there exists the desired initial monad. For this, we follow a track opened by Matthes and Uustalu [16]: we introduce a notion of strengthened arity and prove that the corresponding signatures have initial semantics (i.e. associated syntax). Our strengthened arities admit colimits, which allows the treatment of the λ-calculus with explicit substitution in the spirit of [12].

Initial Semantics for Strengthened Signatures / André Hirschowitz; Maggesi Marco. - In: ELECTRONIC PROCEEDINGS IN THEORETICAL COMPUTER SCIENCE. - ISSN 2075-2180. - ELETTRONICO. - 77:(2012), pp. 31-38. (Intervento presentato al convegno Fixed Points in Computer Science tenutosi a Tallinn, Estonia nel 24 marzo 2012) [10.4204/EPTCS.77.5].

Initial Semantics for Strengthened Signatures

Maggesi Marco
2012

Abstract

Abstract: We give a new general definition of arity, yielding the companion notions of signature and associated syntax. This setting is modular in the sense requested by [12]: merging two extensions of syntax corresponds to building an amalgamated sum. These signatures are too general in the sense that we are not able to prove the existence of an associated syntax in this general context. So we have to select arities and signatures for which there exists the desired initial monad. For this, we follow a track opened by Matthes and Uustalu [16]: we introduce a notion of strengthened arity and prove that the corresponding signatures have initial semantics (i.e. associated syntax). Our strengthened arities admit colimits, which allows the treatment of the λ-calculus with explicit substitution in the spirit of [12].
2012
Electronic Proceedings in Theoretical Computer Science, EPTCS
Fixed Points in Computer Science
Tallinn, Estonia
24 marzo 2012
André Hirschowitz; Maggesi Marco
File in questo prodotto:
File Dimensione Formato  
Hirschowitz and Maggesi - 2012 - Initial Semantics for Strengthened Signatures.pdf

accesso aperto

Descrizione: Originale da ArXiv
Tipologia: Pdf editoriale (Version of record)
Licenza: Creative commons
Dimensione 193.62 kB
Formato Adobe PDF
193.62 kB Adobe PDF

I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificatore per citare o creare un link a questa risorsa: https://hdl.handle.net/2158/605825
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? ND
social impact