No CrossRef data available.
Article contents
Complete algebraic semantics for second-order rewriting systems based on abstract syntax with variable binding
Published online by Cambridge University Press: 14 October 2022
Abstract
By using algebraic structures in a presheaf category over finite sets, following Fiore, Plotkin and Turi, we develop sound and complete models of second-order rewriting systems called second-order computation systems (CSs). Restricting the algebraic structures to those equipped with well-founded relations, we obtain a complete characterisation of terminating CSs. We also extend the characterisation to rewriting on meta-terms using the notion of $\Sigma$ -monoid.
Keywords
- Type
- Special Issue: The Power Festschrift
- Information
- Mathematical Structures in Computer Science , Volume 32 , Special Issue 4: The Power Festschrift , April 2022 , pp. 542 - 573
- Copyright
- © The Author(s), 2022. Published by Cambridge University Press