On the construction of free algebras for equational systems
type: Item
instance of: scholarly article
title: On the construction of free algebras for equational systems
zbMATH Open document ID: 1170.18006
author: Chung-Kil Hur
author: Marcelo P. Fiore
published in: Theoretical Computer Science
publication date: 2009-04-29T00:00:00Z
review text: The authors define a general concept of an equational system \(\mathbb S\) on a category \({\mathcal C}\): it is given by two endofunctors \(\Sigma,\Gamma\) on \({\mathcal C}\) (the ``functorial signature'' and the ``functorial context'', respectively) and two functors \(L,R:\Sigma\)-\({\mathcal A}lg\to \Gamma\)-\({\mathcal A}lg\) (the ``functorial equations'') with \(U_\Gamma \circ L=U_\Gamma\circ R= U_\Sigma\) (where the \(U_\times\) are the appropriate forgetful functors). The category \(\mathbb S\)-\({\mathcal A}lg\) of \(\mathbb S\)-algebras is then defined as the equalizer of \(L\) and \(R\). All details are given to show how this (strictly) generalizes the concept of enriched algebraic theory. The main results give some colimit conditions on \({\mathcal C},\Sigma\) and \(\Gamma\) sufficient for the free algebras to exist and be contructible in a certain carefully described way. These conditions also imply that the forgetful functor \(\mathbb S\)-\({\mathcal A}lg\to {\mathcal C}\) is monadic and that \(\mathbb S\)-\({\mathcal A}lg\) is cocomplete. Applications to concepts recently defined in the theoretical computer science community are treated in details, for example the Pi-calculus, the \(\Sigma\)-monoids and the nominal equational logic.
Mathematics Subject Classification ID: 18C05
Mathematics Subject Classification ID: 08B20
Mathematics Subject Classification ID: 68Q85
Mathematics Subject Classification ID: 03B70
zbMATH DE Number: 5549393
zbMATH Keywords: equational system
zbMATH Keywords: algebra
zbMATH Keywords: free construction
zbMATH Keywords: monad
reviewed by: Michel Hébert
MaRDI profile type: Publication
full work available at URL: j.tcs.2008.12.052
OpenAlex ID: W2102036964
cites work: Q4843177
cites work: Q4044767
cites work: Q3996444
cites work: Q3682648
cites work: Q4314472
cites work: Q4499311
cites work: Nominal equational logic
cites work: On closed categories of functors
cites work: Equational Systems and Free Constructions (Extended Abstract)
cites work: A fully abstract model for the \(\pi\)-calculus.
cites work: Datatype laws without signatures
cites work: A Formal Calculus for Informal Equality with Binding
cites work: A new approach to abstract syntax with variable binding
cites work: Q4825543
cites work: Dualising initial algebras
cites work: Programming Languages and Systems
cites work: Q3907039
cites work: A note on actions of a monoidal category
cites work: Adjunctions whose counits are coequalizers, and presentations of finitary enriched monads
cites work: Strong functors and monoidal monads
cites work: Q5639839
cites work: Concrete domains
cites work: Algebraic operations and generic effects
cites work: Computational effects and operations: an overview
cites work: Q4704209
cites work: The semantics and proof theory of the logic of bunched implications
cites work: Variations on algebra: Monadicity and generalisations of equational theories
cites work: Foundations of Software Science and Computational Structures
cites work: Q4256309
DOI: 10.1016/J.TCS.2008.12.052
Recommended article: Equational Systems and Free Constructions (Extended Abstract)
Recommended article: Free set algebras satisfying systems of equations
Recommended article: Free equivalential algebras
Recommended article: Q4793203
Recommended article: The equational theory of union-free algebras of relations
Recommended article: A dynamic programming method for building free algebras
Recommended article: Q5479929
Recommended article: Q3317089
Recommended article: Equational axiomatization of algebras with structure
Recommended article: An algebraic treatment of quantifier-free systems of arithmetic
description: scientific article; zbMATH DE number 5549393