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

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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, Published 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.
Series
Electronic Notes in Theoretical Computer Science, ISSN 1571-0661 ; 33
Keyword [en]
constraint satisfaction, CSP, coalgebra, adjunctions
National Category
Computer Science
Identifiers
URN: urn:nbn:se:liu:diva-24615DOI: 10.1016/S1571-0661(05)80341-XLocal ID: 6791OAI: oai:DiVA.org:liu-24615DiVA: diva2:244937
Conference
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 texthttp://citeseer.ist.psu.edu/499132.html

Authority records BETA

Angelsmark, Ola

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

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 30 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf