Constraints, Adjunctions and (Co)algebras

✍ Scribed by Ola Angelsmark

• Book ID: 104445442
• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 486 KB
• Volume: 33
• Category: Article
• ISSN: 1571-0661
• DOI: 10.1016/s1571-0661(05)80341-x

✦ Synopsis

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.