Distributivity and residuation for lexicographic orders

Residuation theory concerns the study of partially ordered algebraic structures, most often just monoids, equipped with a weak inverse for the monoidal operator. One of its areas of application is constraint programming, whose key requirement is the presence of a distributive operator for combining...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2022-08, Vol.177, p.106271, Article 106271
Main Authors: Gadducci, Fabio, Santini, Francesco
Format: Article
Language:English
Subjects:
Formal methods
Lexicographic orders
Residuation theory
Soft constraints
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Residuation theory concerns the study of partially ordered algebraic structures, most often just monoids, equipped with a weak inverse for the monoidal operator. One of its areas of application is constraint programming, whose key requirement is the presence of a distributive operator for combining preferences. The key result of the paper shows how, given a residuated monoid of preferences, to build a new residuated monoid of (possibly infinite) tuples based on lexicographic order. •Residuation theory concerns the study of partially ordered algebraic structures equipped with a weak inverse.•Preference structures in several (soft) Constraint Programming (CP) frameworks adopt algebraic structures.•We extend residuation to lexicographic orders of preferences.•As far as we know, no soft CP framework allows for residuation in such orders.•This allows the use of a preference-removing operator in solving algorithms (e.g., arc consistency).
ISSN:0020-0190
1872-6119
DOI:10.1016/j.ipl.2022.106271