Page 136 - 4495

Компаратор «краще за порядком». Для цього компаратора клас
напівкільцевої CSP може бути заданий за допомогою удосконалення
ієрархії (див. означення 14). Для кожної ІО C з ваговою функцією w
потрібно збудувати нову ІО шляхом удосконалення ієрархії C w.
/
Клас напівкільцевої CSP для компаратора типу «краще за порядком»
відповідає класу напівкільцевої CSP для компаратора «локально кра-
ще».

Регіональні компаратори
Компаратори «регіонально краще» порівнюють присвоєння, не
порівнювані локальними компараторами. Присвоєння можуть бути не

порівнювані за рівнями до певного k  1, а на рівні k функції помилок
обмежень порівнюється індивідуально. Ця непорівнюваність повинна
бути включена в адитивну операцію c - напівкільця, яка використо-

вується для порівняння окремих напівкільцевих значень (a  b якщо
S
a b b  ). Покажемо, що жодна адитивна операція, включаючи дану
непорівнюваність, не буде асоціативною. Відповідно до такої власти-

вості, неможливо задати ІО з регіональним компаратором як клас на-
півкільцевої CSP.
Доведемо від супротивного. Нехай маємо ієрархію обмежень

C C  C  { , , } { , , }c c c  c c c . Для присвоєння  зі значеннями функ-
1 2 1 2 3 4 5 6
)
ції помилок (e c для i  1 6 , ступінь задоволення E (C буде мати
)
i
вигляд:
(c
)
 ( e c ) e  ) (e c  
3
1
2
  .
(c
(c
 ( e c  ) e  ) e  ) 
6
5
4
Візьмемо три можливі присвоєння  ,  ,  з ієрархії C з наступ-
ними значеннями функцій помилки та ступенів задоволення, кожне з
яких напівкільцевим значенням a, b, c.
 0 0 1  1 0 1   0 1 0
E (C     a E (C     b E (C     c
)
)
)
 0 1 1   0 0 0   0 0 1 
Відповідно до визначення регіонального компаратора,  повинно
мати напівкільцеве значення з більшою преференцією, ніж
 (a b a  ), так само і  повинно мати більшу преференцію, ніж
 (a c c  ). Маємо (a b ) c a c c    . Аналогічно отримуємо

a  (b c ) a b a   , оскільки присвоєння  повинно мати більше на-
півкільцеве значення, ніж  .

 0 0 1  1 0 1    0 1 0  0 1 0


          [a b ] c c 
  0 1 1   0 0 0   0 0 1   0 0 1 

136