liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Constraints, adjunctions and (Co)algebras
Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory.
2000 (English)In: Electronical Notes in Theoretical Computer Science, ISSN 1571-0661, Vol. 33Conference paper (Other academic)
Abstract [en]

The connection between constraints and universal algebra has been looked at in, e.g., Jeavons, Cohen and Pearson, 1998, and has given interesting results. Since the connection between universal algebra and category theory is so obvious, we will in this paper investigate if the usage of category theory has any impact on the results and/or reasoning and if anything can be gained from this approach. We construct categories of problem instances and of solutions to these, and, via an adjunction between these categories, note that the algebras give us a way of describing 'minimality of a problem,' while the coalgebras give a criterion for deciding if a given set of solutions can be expressed by a constraint problem of a given arity. Another pair of categories, of sets of relations and of sets of operations on a fixed set, is defined, and this time the algebras we get give an indication of the 'expressive power' of a set of constraint types, while the coalgebras tell us about the computational complexity of the corresponding constraint problem. © 2000 Published by Elsevier Science B.V.

Place, publisher, year, edition, pages
2000. Vol. 33
National Category
Engineering and Technology
URN: urn:nbn:se:liu:diva-47517DOI: 10.1016/S1571-0661(05)80341-XOAI: diva2:268413
Available from: 2009-10-11 Created: 2009-10-11

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Angelsmark, Ola
By organisation
The Institute of TechnologyTCSLAB - Theoretical Computer Science Laboratory
In the same journal
Electronical Notes in Theoretical Computer Science
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 18 hits
ReferencesLink to record
Permanent link

Direct link