Substitution in Non-wellfounded Syntax with Variable Binding

By Ralph Matthes, Tarmo Uustalu. 2003

53 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Benedikt Ahrens
2. Benedikt Ahrens
3. Ralph Matthes
4. Marco Maggesi
5. André Hirschowitz

In Computational Theory and Mathematics

1. Benedikt Ahrens
2. Benedikt Ahrens
3. Marco Maggesi
4. André Hirschowitz
5. Ralph Matthes

Citations in the corpus

• Heterogeneous substitution systems revisited (2016, positive): “We then show that the construction of a monad from a heterogeneous substitution system from [23] extends functorially to morphisms.”
• Modules over monads and initial semantics (2010, unknown): “Let us also mention the contributions [11, 18 ] where a much more general notion of signature than ours is treated in a (higher-order) algebra-oriented approach.”
• Modules over Monads and Linearity (2006, background): “[2, 11, 18]) although some other settings have been considered.”