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].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.