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: Coalgebraic Methods in Computer Science CMCS-2000,2000, Science Direct , 2000, 3-12 p.Conference paper (Refereed)
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.

Place, publisher, year, edition, pages
Science Direct , 2000. 3-12 p.
, Electronic Notes in Theoretical Computer Science, ISSN 1571-0661 ; 33
Keyword [en]
constraint satisfaction, CSP, coalgebra, adjunctions
National Category
Computer Science
URN: urn:nbn:se:liu:diva-24615DOI: 10.1016/S1571-0661(05)80341-XLocal ID: 6791OAI: diva2:244937
CMCS'2000, Coalgebraic Methods in Computer Science, Berlin, Germany, 25–26 March, 2000
Available from: 2009-10-07 Created: 2009-10-07 Last updated: 2014-12-18

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
Computer Science

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: 28 hits
ReferencesLink to record
Permanent link

Direct link