Abstract
Inspired from the recent developments in theories of non-wellfounded syntax (coinductively defined languages) and of syntax with binding operators, the structure of algebras of wellfounded and non-wellfounded terms is studied for a very general notion of signature permitting both simple variable binding operators as well as operators of explicit substitution. This is done in an extensional mathematical setting of initial algebras and final coalgebras of endofunctors on a functor category. In the non-wellfounded case, the fundamental operation of substitution is more beneficially defined in terms of primitive corecursion than coiteration.
| Original language | English |
|---|---|
| Pages (from-to) | 191-205 |
| Number of pages | 15 |
| Journal | Electronic Notes in Theoretical Computer Science |
| Volume | 82 |
| Issue number | 1 |
| DOIs | |
| Publication status | Published - Jul 2003 |
| Event | CMCS'03, Coalgebraic Methods in Computer Science Satellite Event for ETAPS 2003) - Warsaw, Poland Duration: 5 Apr 2003 → 6 Apr 2003 |
Bibliographical note
Funding Information:1 Attending ETAPS’03 was partially financed by an EC HSC grant. 2 [email protected] 3Supported by the Portuguese Foundation for Science and Technology under grant No. PRAXIS/C/EEI/14172/98 and by the Estonian Science Foundation under grant No. 5567. The work was largely done while the author was with Dep. de Informática, Universidade do Minho, Braga, Portugal. His visit to LMU München in Jan. 2002 was financed by the Graduiertenkolleg “Logik in der Informatik” of the Deutsche Forschungsge-meinschaft. Attending ETAPS 2003 was made possible by a travel grant from the Estonian Information Technology Foundation. 4 [email protected]
Other keywords
- Final coalgebra
- Functor category
- Monad
- Non-wellfounded syntax
- Primitive corecursion
- Substitution
- Variable binding