Page 131 - 4495

менами, будемо вважати домени у всіх наступних ІО скінченними.
Основні напівкільцеві структури описані для всіх класів у таблиці 1, а
їх деталі – продовженні даного розділу. Інші компаратори («краще в
найгіршому випадку», «регіонально краще») будуть показані як не-

сумісні з властивостями c- на півкільця (монотонність операції  над
 , асоціативність  відповідно). Кожна ІО складається з декількох
S
рівнів м’яких обмежень і одного рівня строгих.

Таблиця 1 – Компаратори ІО з специфікацією < +, ×, 0, 1 >

Клас напів-
кільцевої Компаратор +  0 1
CSP
«краще за незадоволе-

ним»

«краще за сумарною   
Вагова CSP min  0
вагою» 
«краще за найменши-
ми квадратами»
Лексико - «лексикографічно   

графічна CSP краще» minlex т  
«локально-предикатно   
краще» min т  

Локальна «локально-матрично min lex  

CSP краще» т  
  
«краще за порядком» min lex т  

Для моделювання задоволення строгих обмежень у напівкільце-
вої CSP, додається елемент , що виражає 0, а операція  розширю-
ється так, щоб  був її абсорбуючим елементом. Кожне стороге об-

меження має власне напівкільцеве значення, рівне  для всіх корте-
жів, що виражає неможливість нехтування ним. Напівкільцеві зна-
чення інших кортежів не має жодного значення для строгих обме-

жень, найбільш значимим напівкільцевим значенням для цих корте-
жів буде максимальний елемент 1. Окремі рівні C , ,C м’яких обме-
1 h
жень змодельовані за допомогою h-кортежів, що позначаються як
 
a ( , , )a  a або як ( , ,AA  A ) відповідно до значимості елементів кор-
1 h 1 h
тежу.
Глобальні компаратори

131