Äîêóìåíò âçÿò èç êýøà ïîèñêîâîé ìàøèíû. Àäðåñ îðèãèíàëüíîãî äîêóìåíòà : http://www.intsys.msu.ru/magazine/archive/v15(1-4)/shcherbina-053-170.pdf Äàòà èçìåíåíèÿ: Tue Nov 13 10:32:48 2012 Äàòà èíäåêñèðîâàíèÿ: Thu Feb 27 22:28:58 2014 Êîäèðîâêà: Ïîèñêîâûå ñëîâà: m 77

. .



() . , . . . , , , , , . , . . : , , , .
FWF, No. P20900­N13



54

. .

1.
1.1.
() , , [45], [13], , , . () (constraint satisfaction problem) [142], [171], [364]. . , . , , [138]. NP-. , [240] [343], [166], [74], [49], [308], [321], [357], [157], [289], (VLSI) [211], [294] [31]. , [196], [247]. , [125], [161], [225], [241]. [9]. , , , ,




55

, [76], [77], [89], [94], [95], [125], [161], [234], [244], [314]. , (. [19], [266], [322], [377]). , [125], [263], [266], [364]. , , (SAT) , , BANDWIDTH (). ( ). , (Biggs et al., 1986) [67], ( ) 1852 . , (Appel & Haken, 1977) [33]. , ( ) , . , . (, ), (, ). . . Sketchpad (Sutherland, 1963) [356],


56

. .

. . (b elief maintenance) ((de Kleer, 1989 ) [130]; (Dechter, 1987) [131]; (Dechter & Dechter, 1988) [132]; (Doyle, 1979) [152]; (McDermott, 1991) [272]), ((Nadel, 1989) [293]), ((Al len, 1984) [30]; (Rit, 1986) [319]; (Tsang, 1987) [363]), ((Bruynooghe, 1985) [87]; (Fow ler & Haralick, 1983) [165]; (McGregor, 1979) [273]; (Ul lman, 1976) [366]), ((Ginsberg & McAl lester, 1994) [190]; (Zabih & McAl lester, 1988) [387]), ((Borning et al., 1989) [79]; (van Hentenryck, 1989) [368]), ((Kuipers, 1994) [254]; (Miguel & Shen, 1998) [282]; (Shen & Leitch, 1993) [341]), ((Stal lman & Sussman, 1977) [355]), [277], (Bartak, 1997) [51]. [73], [117], [331] [148]. , (Kumar, 1992) [255], (Dechter & Frost, 1999) [138], (Bartak, 2001) [46], [278], [284], (Dechter, 1992) [135], [214] (Mackworth, 1992) [263]. , , , , [1], [5], [6], [8], [7], [10], [11], [14], [15], [16], [17], [18], [20], [22], [24]. , , [34], [142], [176], [266], [324], [368], [371], [374], [376]. , ., . : . 2 .: . . .: ,




57

2006. 1408 . [12]. 2000 . [19]. . . Monta-nari [289] , , (networks of constraints). , - , . Dechter [142], , . . (Mackworth [263]).

1.2.
, , : , , , , , , , [194]. , , , [212], [213]. , 2LP [270], [271], [127], .


58

. .

, . , , , , , . , , , . 1.2.1. SAT (Walsh, 2000) [382]. . =< , , >1 SAT . , . , , . () ¯ , ¯ , , . ( ,0 ,1 . . . , ), , . 1.2.2. , [253]. 1. . . ? , , , , , .
= { 1, . . . , } ,
1

, = { 1, . . . , } = { 1, . . . , } .






59

2. 3- (3-SAT) [3], [300] , , 3 ( ), , , . = 1 , . ( , {0, 1}, ), , {( 1 , 1 ), . . . , ( , )}, ( , ) : , , , ( = 1, . . . , ). , . , 3- . 3. . , , 1 ( 1 ) ( ), ( ) , (1 ). , [332]. (), [247], . 4. . , , , . , , . [196], [247], , , 1 , 1 , . . . , -


60

. .

. , : , , , , . , , . , . 5. , , (. [161], [197], [247]). = ( 1 , . . . , ) , , . = ( ; 1 ,..., ) = ( ; 1 ,..., ) . : , 1 , (( 1 ), . . . , ( )) , ( 1 , . . . , ) . : . , , , , , . , . 6. . , , , , , . , , . (), [29], . 13 , 13 , .




61

213 = 8192 . : , . 7. SEND MORE MONEY : SEND + MORE MONEY 8 , 8 , , , . , (), , , , . . , , , , : = 0, = 0. , 1, = 1. , = 1 , 9. , 0, = 0. , , = 0 , , = + 1. , : = 5, = 6, = 7, = 8, = 2. ( alldifferent). . . : { , , , , , , , } : {0, 1, . . . , 9}


62

. .

: 1 : , { , , , , , , , }, = 2: = 0 or =1 3 : (1000â +100â +10â + )+ (1000â +100â +10â + ) = = (10000 â + 1000 â + 100 â + 10 â + ) . : { , , , , , , : , , , , , , = 0, 1 { 1, 2, 3}, : 1: , { , , , , , , 2: = 0 or =1 3 : + = 10 â 1 + 4 : + + 1 = 10 â 2 + 5 : + + 2 = 10 â 3 + 6: + + 3 = 10 â + , 5, PROLOG.

, } + { 1, 2, 3} ,, = 0, . . . , 9

, },

=



8. . â , (. . 1). : : ( ) {1, . . . , } : = , ( ) = ( ) & - = ( ) - ( ). . 9. . [142]. () . , . , -




63

A 1 2 3 4 5 6 7 8

B

C

D

E

F

G

H

. 1. 8 . , .

1

2

3

4

5

6

7

8

9

10

11

12

13

. 2. . . , (. . 2) ( = 1, . . . , 13). 1 , . . . , 13 , . , [142]:


64

. .

1,2,3,4,5

3,

= {( , , , , ), ( , , , , ), ( , , , , (, ,, 6,9,12 = {( , , , ), ( , , , ), ( , , , ), ( , 5,7,11 = {( , , ), ( , , ), ( , , ), ( , , ), ( 8,9,10,11 = 3,6,9,12 , 10,13 = {( , ), ( , ), ( , ), ( 12,13 = 10,13 .

), , ), ( , , , , )}, , , ), ( , , , )}, , , ), ( , , )}, , )},

10. . , (). , , . . , [367]. 1, 2, 3, 4, 5, . 1:00, 2:00 3:00. , , 1 3, 3 4 5, 2 , 1 4, 4 2:00. , , {1:00, 2:00, 3:00}. . 3. 11. . [384] , -, . 3- 2- . , , (+), (-) (<). .




65

DT4={(1:00, 3:00)}.

T1
RT2,T1={(1:00, 2:00), (1:00, 3:00), (2:00, 1:00), (2:00, 3:00), (3:00, 1:00), (3:00, 2:00)},

T2

T5

RT2,T4={(1:00, 2:00), (1:00, 3:00), (2:00, 1:00), (2:00, 3:00), (3:00, 1:00), (3:00, 2:00)}, RT1,T3={(2:00, 1:00), (3:00, 1:00), (3:00, 2:00)}, RT3,T4={(1:00, 2:00), (1:00, 3:00), (3:00, 2:00)}, RT3,T5={(2:00, 1:00), (3:00, 1:00), (3:00, 2:00)}.

T3

T4

. 3. .

++ + + +

+

. 4. .

( 3 , ), . , , . , . ( Waltz [384]) .


66

. .

+ < < -

+ -

Figure 2 . 5. .

, 5.

2.
2.1.
2.1.1. . , , ( ). . , 1, , 1 , . . . , 8 1, . . . , 8, {1, 2, 3, 4, 5, 6, 7, 8}. Bartak [47], , 95% . , ( ), . , , . NP- , 3- 3 .




67

, , , . . , , , . , . . , 1 , , 3 , 1+5 3. , , , . . , . , , . () = { 1 , . . . , }, , . , . . = { 1 , . . . , }, â â . (scop e) 1 . . , , - .


68

. .

. . = { 1 , . . . , } 1 , . . . , . , , ( ). = 1 â ... â , . , . . () = { 1 , . . . , }, () (1) ={ ,..., } ( = 1, . . . , ), . ( , ), , . ( , , ), = { 1, . . . , } , = { 1, . . . , } , = { 1, . . . , } . , . . 2.1.2. 1 , 2 . 1 2 , , 1 2 . 1 2 , , 1 , 2 , . 1 - 2 , , 1 , 2 . ( ) ( ) , -




69

, . , . . , . , : (1) ; (2) , , ; (3) , , . . .

2.2.
. , . , , , . . , = . , ; . . , (. 1). , . SEND+MORE=MONEY 7 1, - ( , , , , , , , ). , = .


70

. .

2.2.1. [325]. : , ( ) , . -, . . , all-different , . , , (bipartite matching) , , . , : , . , , . all-different atmost , , . , , . . . -, . -, , . , ( ) ,




71

, . all-different- ( 2 ) [311]. alldifferent-, , . all-different- . CHIP [27], (. [58]). (global cardinality constraint (gcc)) [312] [27]. , , , , . , , , , , . , . 2.2.2. , . , , , , , , , . (overconstrained) [223]: ,


72

. .

. , , ( !), , , . (soft constraint) [50]: (), , , . . , , , . [79], , . [154], [328], [160], [333] , 0 1. [235] . [172] , , , .

, [68], [69], [70] ( ), (valued constraint), [98], [143], [334]. , , .




73

2.2.3. , . , all-different = , = . . Dechter & Pearl [141]. XIX (Peirce). Peirce [302] . Rossi et al. [323] Peirce [302] , , . Dechter (1990) [134] Bacchus & van Beek [39].

2.3.
2.3.1. , , : () , , . . ( , , ) = ( , ), , , ( - ). , .


74

. .

x1, D1={4, 5} a)

>

x2, D2={3, 4, 5} b) =

x2 x1 > x2 x x2 = x4 x

>

2

2

x2 > x3 x3, D3={1, 2} x4, D4={4, 5}

. 6. a) b) . . , , - , , ( ). 2, . , , . , , , [239]. 2 , , . . , , ( c- )
2 : = ( , ) [4] ( ) = ( , ) , ( ) , . , ( ) .




75

. , . , .

2.3.2. (induced width) , . . . . ( , , ), = , = ( , ). = ( , ) : {1, 2, . . . , }, , (-1 (1), -1 (2), . . . , -1 ( )). , , , , . . . = ( , ) , . , ( ). . , . , 1, - 1. :


76

. .

. , . Dechter & Pearl [140] . . = ( , ) , = ( , ) , , { , } , { , } , ( ) < ( ), ( ) < ( ), = , { , } . , ; , . . . () = ( , ) ( , ) . . , . [23]. -3 . Dechter & Pearl [140] , , . 2.3.3. . , , 4 . . , ,
- [38].
3

, -




77

NP- , . ( ) max-cardinality 4 . max-cardinality , , : . , , . . max-cardinality . , , , max-cardinality . , ( , , ). , , . , max-cardinality , , , . . , .

3.
3.1.
[329]: 1) . , . . 2) , , 4

max-cardinality

.


78

. .

. , , , , , , , . 3) , . , , . , . . : , , ; , . .

3.2. (Backtrack Search)
3.2.1. . , , , , (backtracking)5 . , .
Bitner & Reingold (1975) [71].
5




79

. , . . Generate and Test , , . 6 . , . , , . , , . , / . , , . , , . , (Mackworth, 1977) [262]. (chronological backtracking) (Bitner & Reingold, 1975) [71]. , . , , . ,
6



.

, -


80

. .

. . 7 . , , , . ( , ). : . Assignments [ ]. , . [ ]. - , .
Procedure BT(i) Foreach Val In D[i] Assignments[i]:= Val Consistent:=True For h:=1 To i-1 While Consistent Consistent:=Test(i,h) If Consistent If i=n Show - Solution() Else BT(i+1) Return False End Procedure

. 7. . ( , ) , ( , ) . ( , ) , Test( ) ( ). , 1 , . . . , -1 . , -




81

. ( ), - 1 -1 . , -2 , . . , . ( ), BT( + 1) , , . .

-«

» 4 4 3 2 1 5 3 2 1 4 1 x2 x3 5 x1

4 4 54 5 4 5 4 5

x4

. 8. . . 8 , , . 6. ( , - ) , - ( ) . . , . .


82

. .

, , ´ . 3.2.2. (Gaschnig, 1979) [181] : . , ( , ) , . , , < < . . 6. . 8 ( 2 , 4 ). ( ). 3.2.3. (intelligent backtracking) [42], [86] , , , . , , , { + 1, . . . , } , , . , - 1, , , .




83

(backjumping), , (conflict-directed backjumping), (backchecking), (backmarking). (backjumping) (Gaschnig, 1977, 1979) [180], [181]. . , , -1 . -1 . -1 , -1 , -1 . - (), . - . , : = { 1 , . . . , }. - , 7 , Gaschnig' [181] - , (. . 9). , , - . . , , ,
, .
7

-


84

. .


, . , , = 3, , - 3 . - , - - 1. , +1 , +1 , +1 .

4 4 3 1 1 5 3

5 4 1

x

1

x2 x3

4 4 5 4 5

x4

. 9. . : , , , , , , (Prosser, 1993) [309]. , , . - . , ( - +1 ) , - . , , ,




85

, . (Stal lman & Sussman, 1977) [355] , , (truth maintenance systems) (Doyle, 1979) [152]. (Kleer, 1989) [130]. [355] (constraint recording), , , . (Dechter, 1990 a) [133]. (back-marking) (Gaschnig, 1979) [181], . [181] , , , . , , . . , , . , , ( ), . , , : , ; , . , , ,


86

. .

, , . . , , , - = . , . (, , , , , ). = , < , - - , = . , 10,2 = 4 , 4 -- 10 = 2 1 , 2 , - 3 10 = 2 . , , . . , , , , , = , - , , . - , , = < , . , ; [248] , ( ). (Kirkpatrick et al., 1983) [243], . (minimal conflicts) (Gu, 1989) [200] [285] (Minton et al., 1992). (Sosic & Gu, 1994) [354] 3 000 000 , . . (Cheeseman et al., 1991) [104] , , ,




87

, . , , . . [88] , Prolog, . 3.2.4. 1 , . . . , -1 () (conflict set) . ( () (nogo o ds) . 3.2.5), , . . 6 , (. 8). { 1 = 4, 2 = 3, 3 = 1} 4 . , : . , . (Bruynooghe, 1985) [87] . , . ( ) (Dechter, 1990) [133]: , , . , , (Dep endency Directed Backtracking) (Stal lman & Sussman, 1977 [355]) (truth-maintenance systems) (Doyle, 1979 [152]). :


88

. .

. , . [133] , , ( ) . () : , . , { 1 = 4, 3 = 1}, { 2 = 3}. 3 2 . , , - . . Dechter (1990) [133] . . , . Dechter (1990) [133] . , . , , . Bitner & Reingold MRV, (most-constrained-variable). Brelaz (1979) [82] (degree heuristic) , MRV. , , . Haralick & El liot (1980) [203] . [248] ( Kondrak & van Beek, 1997) .




89

3.2.5. (Dechter, 1990) [133]. () (nogo o d) [238] (conflict set) , . -, , [66]. , . , , , . , . , , . . (Dechter 1990) [133]. , SAT (Bayardo & Schrag 1997) [54]. SAT (), (Moskewicz et al. 2001) [291] . , . , . (learning), , , [138]. , . [309] , , , . [4] , (eliminating explanations), -


90

. .

. [5] . [42], [130], [286], [355], . , , . [238] , . 3.2.6. . , , , ( , ). , . () (dynamic backtracking) (Ginsberg, 1993) [188], [189] , , . , , , , . , , . . , , , ( ).




91

, . ; , , , . , . , , . , (Baker, 1994) [42] , , , . , , , , . .

3.3.
3.3.1. [35]. . , [116]. , , , . , , . - , , .


92

. .

, . [48] , : (constraint relaxation), (filtering algorithms), (narrowing algorithms), (constraint inference), (simplification algorithms) . . , [289], [384], , , [136], [140], [255], [262], [263], [265], [289]. () . , , . , , . Waltz [383], ( ) . , . , , . . . , -




93

. . : , . , . , - , , , . . 3.3.2. . , , . , . (a) , ([167], [262], [289]), (b) , ([262], [289]), (c) , ([128], [179], [203]). , , . , . , -


94

. .

, ( ). , , , , . , , , . , , -, . , , , [262]. 3.3.3. , , : ( ) , , ( ), . (no de-consistency algorithm (NC)), , , ( ), . 8 , ( , ), . , ( , ), . , (
.
8




95

) . . , (Haralick & El liot, 1980) [203] (forward checking), (McGregor, 1979) [273], (Gaschnig, 1979) [181] ; (Sabin & Freuder, 1994) [330] MAC (Maintaining Arc Consistency). , . Mackworth & Freuder [265] , . , (supp ort), , . -, . ( , ), , , ; . . () . , , - . , {0, 1, 2} + = 1. {0, 1}. , , , , - .


96

. .

, . [383], [289], Mackworth [262] : , . (AC-1, AC-2, AC-3) , PC-1, PC-2, PC-3 . Mackworth & Freuder [265], , . (. [65], [262] ). , ´ ( ), , [288]. , . AC-1 ( (Machworth, 1977) [262]. AC-1 AC-2, . . . , AC-7, . AC-1, AC-2, AC-3 Mackworth & Freuder [265]. AC-3 ( 3 ), ´ ( + ), . AC-4 [287] AC-3 ( 2 ). AC-3 AC-5 [369], . AC-7 . : ( 2 ) ; ( , ) ,




97

, ; ( 2 ), ( 2 3 ). 3.3.4. . -- = { 1 , . . . , }, , - , . DAC ( , , ) = { 1 , . . . , } . ( , . . . , 1 ). 9 . , , , , , . [140]. , , . , . 3.3.5. , Montanari [289]. . - (path-consistent), :
9

, ,

.


98

. .

, . , . . PC-4, AC-4, ´ ( 3 3 ). , ( 1 , . . . , ), 1 1 , ( 1 ), ( ), ( 1 , ), : 2 2 , . . . , -1 , , (
2

), . . . , (

-1

), (

1

,

2

), (

2

,

3

), . . . , (

-1 1

, ,

)
2

. . 10 (

,

3

).

x1, D1={4, 5} > a) > x3, D3={2, 3} x2, D2={3, 4} b)

x1, D1={4, 5} > x2, D2={3, 4} > x3, D3={2, 3} {(4, 2), (5, 2), (5, 3)}

. 10. [283]. . 10 a. (. 10 b), 1 = 4, 3 = 3: 2 , -




99

( 1 , 2 ), ( 2 , 3 ). . , , , . 2 -, (Montanari, 1974) [289]. , , . (. . 10). (Montanari, 1974) [289], PC-1 (Mackworth, 1977) [262]. Mackworth [262] PC-1 PC-2. PC-3 (Mohr & Henderson, 1986) [287] AC-4. PC-3 . PC-4 (Han & Lee, 1988) [202] . (Chmeiss & Jegou, 1996) [106]. Mohr & Henderson [287] , AC-4 PC-4, Lauriere [258].

3. 3. 6.

-

, . , , , . -, Freuder [167], [168], [169], .


100

. .

-, ( = 3 , > 3 - ). . ( -). -, - 1 . - , - . - , , . 2- 3-. , - , , , 1-.

3.4.
. [262] , NP-, () . , (. [255], [263], [364]). , ( [141], [170], [326]) [227]. , (backtrack-free search) [136]. , , -




101

(hyp ertree decomp osition), [195]. (constraint language)10 , , , [111], [218], [226], [227], [229], [230], [231], [232]. NP-, , [90], [112], [260], [310]. , ([324], 7). , , , . , : ( ), , [115], [140], , , [90], [161]. , (. [324]). , , , ( ). . , (, ) , ( ) , , [198], [209], [23].
[113]
10




102

. .

. , , . . , , [225]. , . , [125], [161], [225], [252]. , , , [260], [310]. [228], [230], [227], [233] , , . [114], , , . , , , , . , , [146], [306]. , , . , , [225], [227]. ,




103

, , . [96], [92], [93], [91], [126], [228]. : ( , ) [94], 2- [332] 3- [96]. , , [75], [92], [94], [112], [121], [126], [251]. (. 6.4.3 [114]). , , [210], [274], [358]. , 11 , , [2]. , - . , , , , , . [301], , .
( , , )= ( , , )= .
11



,


104

. .

[122] , , , . . , , .

4.
, , (Freuder, 1985) [169], , - . (Beeri et al, 1983) [55]. , . , , . , .

4.1.
. , , (. (Miguel & Shen [283]), 4.4), . , . -




105

. , . , , . / , , , 12 . / ), ; ( ( ), . [12]: = 80 = 20 , , , . , . . , : . . , . 1 , . . . , . , , . 2 ( , ), , . 1 , , , . , , , - .
12

.


106

. .

; , -. , .

4.2.
(cycle cutset) (Dechter, 1990) [133] , . . , ( ) .
x

1

x2

x1

x

2

x

2

a)

b)

x3

x4

x2

x3

x4

. 11. . . 11 a. 2 , , (). (. 11 b), 2 . , .




107

() . , , . NP- . , , , . , , . , , , 20% [284]. , 25% [284]. [12]. , , . . , , : ­ , ; ­ , . , ( ( - ) 2 ). , , , . ( - 2). NP-, .


108

. .

(cutset conditioning).

4.3.
(Dechter & Pearl [140]; Freuder [168]) . , . , . . Even [159] ( ) ( ). , . ( ). Dechter & Pearl [140] ( ), , , , .

4.4.
(tree-clustering) (Dechter & Pearl [141]) - , . - (. (Miguel & Shen [283])), : : , 4 , (, 2 ). : .




109

(Tarjan & Yannakakis [361]), : a) (maximum cardinality) ) , , . 12 a b ( (Dechter & Pearl [141])) . , (. . 13 a).

. 12. . , , . , , , .

. 13. .


110

. .

. 13 b) . ( ), .

4.5.
4.5.1. (Bucket elimination) [137], [142] [64], [21], [22], . . ´ . , , . [257]. 4.5.2.

(Seidel, 1981) [337], . , ( ). 13 (Seidel, 1981) [337] 1 , . . . , , . , . +1 , , , . . . 6 a). :
13



.




111

1 = { 1 }, 2 = { 1 , 2 }, 3 = { 1 , 2 , 3 }, 4 = { 1 , 2 , 3 , 4 }. , : 1 = { 1 }, 2 = { 2 }, 3 = { 2 }, 4 = { }. , , . , .

1
F1

4
4 s0 5 3

3

F2

F3 2 1

F4 s
4

3

3
4

4

5

4

2

4

. 14. . 0 , . . . , , , ( = 0, = ) . 0 , 0 , ( ). -1 ( , -1 ). , -1 , -1 . 0 , , . . 6 a) . 14. -1 . , -1 . ,


112

. .

-1 , . ´ , ( +1 ), , . , . , , . , - 1. , , .

4.6.
(Robertson & Seymour, 1986) [320]. Dechter & Pearl, 1987, 1989) [140], [141], (Freuder, 1985) [169], ( ) , (tree decomp osition) . , . , , , . . . , ( ) . - , , .




113

, . , , , ; . ; - , , . , . , - , . , ; , . , , , . ; , . ; . , +1 ). ( , , , . , NP-, , .

4.7.
(Robertson & Seymour, 1986) [320], (Dechter & Pearl, 1987, 1989) [140], [141], , . ( Gottlob et al., 1999) [195], [196] -


114

. .

, . , ( +1 log ), , , , , , . (Pearson & Jeavons, 1997) [301] , , . [115] , (guarded decomp osition). , , .

5.
5.1.
(constraint programming) . (. (Colmerauer, 1990) [120], (Jaffar & Lassez, 1987) [220], (Van Hentenryck, 1989) [368]) . , , , . . , (. (Harvey & Ginsberg, 1995) [206], (Korf, 1996) [249], (Meseguer, 1997) [279], (Walsh, 1997) [381]), . , , (limited discrepancy search (LDS))




115

. (. (Harvey & Ginsberg, 1995) [206], (Laburthe & Caseau, 1998) [256], (Perron, 1999) [304]), (. (Laburthe & Caseau, 1998) [256], (Perron, 1999) [304], (Schulte, 1997) [336], (Van Hentenryck et al., 2000) [375]). , Oz , (Schulte, 1997) [335]. , . SALSA14 (Laburthe & Caseau, 1998) [256] . (Perron, 1999) [304] , : , , , . , , [97]: , . : , ; , ; , ; , ; , , ; , .
14

SALSA: A Language for Search Algorithms.


116

. .

5.2.
10­15 [266] , . (constraint programming) [81]. [372]. () (Constraint Logic Programming (CLP)) [97] Jaffar & Lassez [220], Marriott & Stuckey [266], [37] . , [116]. ( : - ), , . , , . , , . , , , [261], . (Marriott & Stuckey, 1998) [266] : . (ThingLab [78], Bertrand [259], ALICE [258]), . ,




117

, . (X), , . , , , , , . , ( ) . , , . , [261] , , . , . , , ( ) . , . , , . . , SICStus Prolog [99], ILOG Solver [216], Geco de [183], . , . , , -


118

. .

, ( , , ) . Jaffar & Lassez (1987) [220] , . : PROLOG I I I IV, CLP(R)15 , CHIP16 CLP(BNR)17 .

5.3.
. 1980- Van Hentenryck [368] CHIP [149]. ECLiPSe18 [158], [378] CLP(FD)19 [109]. . (partial search) . , . , , , , ( LDS [206] [57]), . , 2.2 , . , CHIP [149], [56]. , SICStus Pro15 16 17 18 19

CLP(R): Constraint Logic Programming (Reals). CHIP: Constraint Handling in Prolog. CLP(BNR): Constraint Logic Programming (Booleans, Naturals and Reals). ECLiPSe: Constraint Logic Programming System. CLP(FD): Constraint Logic Programming over Finite Domains.




119

log [99], ECLiPSe [158], [378], IF Prolog http://www.ifcomputer.de/ /Pro ducts/Prolog/home_en.html, Oz [207], [353], [204], [292], , CHIP. ( , all-different) [313], [338]. , [43]. , , , . , , , , [380]. , ( ) , . , CLP(FD) , [184].

5.4.
(, , , .). . , [295]. , [62] , ECLiPSe [158], [378], [385] CLP(BNR), Helios [370] Numerica [371] , [295].


120

. .

5.5.
. ( Prolog), , ( C/C++). , (: Helios [370], Numerica [371] OPL [374]). . , FORWARD [191] CHIP [344], . CML20 , [32]: CML- , , CHIP-. VISUAL SOLVER [373], , , . : , , [173]. : , [327], . , (Ab ductive Constraint Logic Programm20

CML: Constraint Modelling Language.




121

ing (ACLP) (. http://www.cs.ucy.ac.cy/aclp/), ECLiPSe [158].

5.6.
, : . , , . [100]. Oz Explorer [335], CHIP [345] ( CHIP [150]), , CIAO [208], 3D- VRML [352], , .

5.7.
[109] CLP(FD), , , CLP(FD,S) 21 [185], - (semiring), . , : , , , . , [98], [143].
CLP(FD,S): Semiring-based Constraint Logic Programming Language over Finite Domains.
21


122

. .

5.8. (Constraint query languages)
( ()), . . , (, () ) , [201], [110]. , , , . , , , - . ( ) (Constraint Databases) [83], [237]. . , . , , [60], [199]. [192], [236], [237], . Datalog [317]. Datalog, [316], , -




123

[84]. [362] .

5.9.
(concurrent constraint programming), , (tell op eration), , , (ask op eration), . , Oz [207], [353], [204], [292], AKL22 [205], [224], [290], CHR23 [175], CIAO [208] , . (Temp oral con-current constraint programming) (nondeterministic temp oral concurrent constraint programming (NTCC)) , . [386] [129].

5.10.
CHIP [149] , [368]. ILOG [216] COSYTEC [123], Prolog I I I [119], [120], Prolog IV [307], CLP(R) [222], ECLiPSe
22 23

AKL: Andorra Kernel Language. CHR: Constraint Handling Rules.


124

. .

[158], [378], CIAO [208], CLP(FD) [109]. , . , , , , , , [368], [377]. . Prolog, 1 SEND+MORE=MONEY: sendmore(Digits) :Digits = [S,E,N,D,M,O,R,Y], Digits :: [0..9], S #\= 0, M #\= 0, alldifferent(Digits), % % % % % % % % % : S 0 : M 0



1000*S + 100*E + 10*N + D + 1000*M + 100*O + 10*R + E #= 10000*M + 1000*O + 100*N + 10*E + Y, labeling(Digits). %

. :: , {0, 1, 2, 3, . . . , 9}. # = 0 # = 0 , 0. , 0 . alldifferent(Digits). , , , , SEND+MORE=MONEY . :




125

B-Prolog ( Prolog, ) http://www.probp.com CHIP V5 ( Prolog, C++ C, ) http://www.cosytec.com/pro duction_scheduling/chip/ /optimization_pro duct_chip.htm Ciao Prolog ( Prolog, : GPL/LGPL) http://clip.dia.fi.upm.es/Software/Ciao/ ECLiPSe ( Prolog, op en source) http://eclipse-clp.org/ SICStus ( Prolog, ) http://www.sics.se/isl/sicstuswww/site/index.html GNU Prolog ( ) http://www.gprolog.org/ Oz http://www.dmoz.org/computers/programming/languages/oz/ YAP Prolog http://www.dcc.fc.up.pt/~vsc/Yap/do cumentation.html SWI Prolog Prolog, http://www.swiprolog.org/ Claire http://www.claire-language.com/cgi-bin/trac.cgi Curry ( Haskell, ) http://www.curry-language.org/ HAL: [147], [145] . : Cho co ( Java, ) http://www.emn.fr/x-info/cho co-solver/doku.php Comet ( C- , , , , ) http://dynadec.com/ Disolver ( C++, ) Geco de (C++ library, : X11 style) http://www.geco de.org


126

. .

ILOG CP Optimizer (C++, Java, .NET libraries, ) http://www.ilog.com/pro ducts/cp optimizer/ ILOG CP ( C++, ) http://www.ilog.com/pro ducts/cp/ JaCoP( Java, op en source) http://jacop.osolpro.com/ JOpt ( Java, ) http://jopt.sourceforge.net/ Koalog Constraint Solver ( Java, ) http://linux.softp edia.com/get/Programming/Libraries/ /Koalog-Constraint-Solver-8073.shtml Minion (C++ program, GPL) http://minion.sourceforge.net/ Python-constraint ( Python, GPL) http://labix.org/python-constraint Cream ( Java, : LGPL) http://bach.istc.kob e-u.ac.jp/cream/ Emma ( Python, ) http://www.eveutilities.com/pro ducts/emma Common Lisp via Screamer ( , CLP(R), CHiP) http://www.cl-user.net/asp/libs/screamer Bertrand [259].

5.11.
, 1970- , (, GAMS (Brooke et al., 1988) [85] MGG (Simons, 1987) [351]), . -, , . -, , , , . ,




127

. , , ACE (Fuchs & Schwitter, 1996) [178], , . , . , ALICE (Lauriere, 1978) [258] , , . . , Eclipse (Gervet, 1994) [186] , ; F , ESRA , NP-Sp ec , , . , . ESSENCE , , , , , . ESSENCE , . . , , , , . , . , , (plug and play) . Zinc, , [268]. Zinc (Marriott et al., 2006), [267]; (de la Banda et al., 2006) [144] , , ESSENCE, , , , ESSENCE, . ESSENCE -


128

. .

: ESRA, F LOCALIZER (Michel & Van Hentenryck, 2000) [281]. , , Z, (Renker & Ahriz, 2004) [315], Z [318]. , Z , , . Z ESSENCE. Alloy (Jackson, 2006) [219] Z . Alloy SAT.

6.
. , American Express, BMW, Co ors, Danone, eBay, France Telecom, General Electric, HP, JB Hunt, LL Bean, Mitsubishi Chemical, Nipp on Steel, Orange, Porsche, QAD, Royal Bank of Scotland, Shell, Travelo city, US Postal Service, Visa,Wal-Mart, Xerox, Yves Ro cher, Zurich Insurance [325]. , , . [221], [348], [349], [377].




129

6.1.
, . , , , . , ( ) ( ) [107], [108], [303], [348].

6.2.
, , , . , , . , , , . , . [102], [103] ( ), [118] ( ), [155], [246], [298].

6.3.
LOCARIM [347] COSYTEC France Telecom: , . PLANETS (PLanning Activities on NETworkS) [124], (University of Catalonia) ,


130

. .

, . [36] CHIP . POPULAR [177], ECLiPSe.

6.4.
, [44], [101]. , , , , , . , [310]. , , ATLAS [346], Monsanto . PLANE [59] Dassault Aviation Mirage 2000 Falcon . MOSES [28], [350] COSYTEC . FORWARDC [191] () [13], CHIP, -




131

, , , . Xerox [174]. (preemptive) , . : , CLAIRE Scheduler , , [296], [297]. ILOG Scheduler [217]. , (, C/C++), (, CHIP), . [41] , : , , , , . , , , . , , , . , , . , [321]. . TAP-AI [52] , SAS. (). OPTISERVICE [118] - RFO.


132

. .

, . MOSAR (http://www.cosytec.com/constraint_programming/cases_studies/administration.htm), Cisi COSYTEC , 200 .

6.5.
. , , - , . , , . . COBRA [350] North Western Trains . DAYSY Esprit ( SAS-Pilot) [52] . [164], . , [269], ILOG . ( ), . , [340], [305] . (Vehicle Routing) .




133

6.6.
. , , , . : SVE (system verification environment) [163], [276], ( 2LP).

6.7.
. , : , ( -), . , ( ), . (The Short Term Planning (STP)) Renault [105] . . , , [min, max]. , ,


134

. .

, . [215]: . , . , ECLiPSe [342].

6.8.
, , . . , . , Banque Bruxelles Lamb ert [153] . (Humb olt University) [193]. [26], [63], [182], [187].

6.9.
. ( ). -




135

. [80]. [360] [359]. , , CAD/CAM [339]. EaCL [365] .

6.10.
: , . , ( ), , , . , , . ( ) [79], [172], [154], [328], [334], [68]. , (, ). , , University of Siegen, Germany [53], ( , ) [72]. , , Neuwied [280].


136

. .

6.11.
( ) [40]. . , NP- . Sony , [299].

7.
, . , , , , , , .


[1] . Prolog, 3- / . . .: , 2004. [2] . . CSP // . 2006. . 45. . 655­686. [3] ., . . .: , 1982. [4] . ., . ., . ., . . . . 2-, . .: , 2009. [5] NeMo+: - /




137

. . [ .] // . . . ('98). . 1998. . 524­530. [6] NeMo+ (, , ) / . . [ .] // -. 7 / , . . . . , , 1998. [7] . . . [ .] // . 1998. 7. . 13­22. [8] - + / . . [ .] // 96 . . I I I. , 1996. . 408­414. [9] . ., . ., . . . , . . , 2005. [10] . . // . 1998. 3. . 40­49. [11] . ., . . : // . 2001, 2. . 60­67. [12] ., . : . 2 . / . . .: , 2006. : http://rriai.org.ru/zadachi-udovletvoreniya-ogranicheniy.html ( 07.08.2010).


138

. .

[13] . ., . . // . : , 2006. . 47­59. [14] . . : . ­03. , 2003. . 19­31. [15] . . . , 2003. (. / ; 2). [16] . . : . . . . .-. (05.13.11 , ). , - . . . , 2007. [17] . . CSP . . . . . .. (05.13.18 , ). , . . . , 2008. [18] . ., . . // . 1998. 3, 2. . 45­53. [19] . ., . . () // : . . . : , 2000. . 7: . . 275­310. [20] . ., . . // . : , 1999. . 262­267. [21] . . // . 2006. 2. . 28­41.




139

[22] . . // . 2007. . 1. . 24­39. [23] . . () // . 2007. 4. . 102­118. [24] . . // 11 (, 28 3 2008 .) .: , 2008. . 2. . 244­252. http://www.raai.org/cai-08/files/cai08_pap er_189.do c ( 07.08.2010) [25] Mo dels and solution techniques for the frequency assignment problems / K. I. Aardal [et al.] // Annals of Op erations Research. 2007. Vol. 153. P. 79­129. [26] Ab dennadher S., Schlenker H. INTERDIP an interactive constraint based nurse scheduler // Pro c. PACLP99, 1999. http://www.pms.ifi.lmu.de/publikationen/PMS-FB/PMS-FB1999-2/PMS-FB-1999-2.p df ( 07.08.2010) [27] Aggoun A., Beldiceanu N. Extending CHIP in order to solve complex scheduling and placement problems // Mathl. Comput. Mo delling. 1993. V. 17. P. 57­73. [28] Aggoun A., Gloner Y., Simonis H. Global constraints for scheduling in CHIP. Invited Industrial Presentation // JFPLC 99, 1999. [29] Allen J. F. Maintaining knowledge ab out temp oral intervals // Comm. ACM. 1983. 26. P. 832­843. [30] Allen J. F. Toward a general theory of action and time // Artificial Intelligence. 1984. V. 23 (2). P. 123­154. [31] Allen J. F. Natural Language Understanding. 2nd edition. Benjamin Cummings, 1994. [32] Andersson K., Hjerp e T. Mo deling Constraint Problems in CML // The Third International Conference on the Practical Application of Constraint Technology (PACT'98), London, 1998. P. 295­312. [33] App el K., Haken W. Every planar map is four colorable: Part I: Discharging // Illinois J. Math. 1977. V. 21. P. 429­490.


140

. .

[34] Apt K. R. Principles of Constraint Programming. New York: Cambridge University Press, 2003. [35] Apt K. R. The essence of constraint propagation // Theoretical Computer Science, 1999. 221 (1­2). P. 179­210. [36] New Trends in Constraints / K. R. Apt [et al.], eds. Joint ERCIM/Compulog Net Workshop, Octob er 1999, Selected pap ers, vol. 1865 of Lecture Notes in Computer Science, Paphos, Cyprus. Springer-Verlag, 2000. [37] Apt K. R., Wallace M. Constraint Logic Programming using Eclipse. New York: Cambridge University Press, 2006. [38] Arnb org S. Efficient algorithms for combinatorial problems on graphs with b ounded decomp osability a survey // BIT. 1985. V. 25. P. 2­23. [39] Bacchus F., van Beek P. On the conversion b etween non-binary and binary constraint satisfaction problems // Pro ceedings of the Fifteenth National Conference on Artificial Intelligence (AAAI­98). Madison: AAAI Press, 1998. P. 311­318. [40] Backofen R. The protein structure prediction problem: A constraint optimization approach using a new lower b ound // Constraints. 2001. V. 6. P. 223­255. [41] Multi-criteria comparison b etween algorithic, constraint logic and sp ecific constraint programming on a real scheduling problem / A. Bachelu [et al.] // Pro c. PACT97, 1997. [42] Baker A. B. Intelligent backtracking on constraint satisfaction problems: Exp erimental theoretical results. Ph.D. Thesis, Graduate Scho ol of the University of Oregon, 1995. [43] Baptiste P., Le Pap e C., Peridy L. Global constraints for partial CSPs: a case- study of resource and due date constraints // Pro c. 4th Int. Conf. on Principles and Practice of Constraint Programming (CP98). Springer-Verlag, LNCS 1520, 1998. [44] Baptiste P., Le Pap e C., Nuijten W. Constraint-Based Scheduling: Applying Constraint Programming to Scheduling Problems. Dordrecht: Kluwer Academic Publishers, 2001.




141

[45] Barnier N., Brisset P. Graph coloring for air traffic flow management // Annals of Op erations Research. 2004. V. 130. P. 163­178. [46] Bartak R. Theory and practice of constraint propagation // Pro ceedings of the Third Workshop on Constraint Programming for Decision and Control (CPDC­0I). Poland, Gliwice, 2001. P. 7­14. [47] Bartak R. Constraint Programming: In Pursuit of the Holy Grail // Pro ceedings of the Week of Do ctoral Students (WDS99), Part IV. Prague: MatFyzPress, 1999. P. 555­564. [48] Bartak R.Theory and Practice of Constraint Propagation // Pro ceedings of the 3rd Workshop on Constraint Programming for Decision and Control (CPDC2001), Poland, Gliwice: Wydavnictvo Pracovni Komputerowej, 2001. P. 7­14. [49] Bartak R. Constraint-based Scheduling: An Intro duction for Newcomers. // Intelligent Manufacturing Systems 2003. A Pro ceedings volume from the 7th IFAC Symp osium / L. Monostori, B. Kadar, G. Morel (eds.) (6­8 April, 2003, Budap est, Hungary). Elsevier Science, 2003. P. 69­74. [50] Bartak R. Mo delling soft constraints: A survey // Neural Network World. 2002. Vol. 12, N 5. P. 421­431, [51] Bartak R. Exp ert Systems Based on Constraints (in Czech, English abstract), Do ctoral Dissertation. Prague, Charles University, April 1997. [52] Baues G., Kay P., Charlier P. Constraint based resource allo cation for airline crew management // Pro c. ATTIS'94, 1994. [53] Priority-driven constraints used for scheduling at universities / M. Baumgart [et al.] // Pro c. PACT97, 1997. [54] Bayardo R. J., Schrag R. C. Using CSP lo okback techniques to solve real-world sat instances // Pro c. of the AAAI National Conference. 1997. P. 203­208. [55] On the desirability of acyclic database schemes / C. Beeri [et al.] // Journal of the Asso ciation for Computing Machinery. 1983. V. 30 (3). P. 479­513.


142

. .

[56] Beldiceanu N., Contejean E. Intro ducing global constraints in CHIP // Journal of Mathematical and Computer Mo deling. 1994. V. 20. P. 97­123. [57] Partial search strategy in CHIP / N. Beldiceanu [et al.] // Pro c. 2nd Int. Conf. on Meta-Heuristics. France, Sophia-Antip olis, 1997. [58] Beldiceanu N. Global constraints as graph prop erties on structured network of elementary constraints of the same typ e. Technical Rep ort T2000/01, SICS, 2000. [59] Bellone J., Chamard A., Pradelles C. Plane an evolutive planning system for aircraft pro duction // Pro c. 1st Int. Conf. on Practical Applications of Prolog (PAP92), 1992. [60] Belussi A., Bertino E., Catania B. Manipulating spatial data in constraint databases // Pro c. 5th Symp. on Spatial Databases. Springer-Verlag, LNCS 1262, 1997. [61] Benhamou F., Older W. Applying interval arithmetic to real, integer and b o olean constraints // Journal of Logic Programming. 1997. V. 32 (1). P. 1­24. [62] Benhamou F., Van Hentenryck P. (eds.). Sp ecial Issue on Interval Constraints // Constraints: An International Journal. 1997. V. 2, N 2. [63] Berger R. Constraint-based gate allo cation for airp orts // Pro c. ILOG User- group meeting, 1995. [64] Bertele U., Brioschi F. Nonserial Dynamic Programming. New York: Academic Press, 1972. [65] An optimal coarse-grained arc consistency algorithm / C. Bessi`re e [et al.] // Artificial Intelligence. 2005. V. 165. P. 165­185. [66] Bessi`re C. Constraint propagation. Chapter 4 in Rossi F., van e Beek P., Walsh T. (Eds.) Handb o ok of Constraint Programming. Elsevier, 2006. P. 29­83. [67] Biggs N. L., Lloyd E. K., Wilson R. J. Graph Theory 1736­1936. Oxford: Oxford University Press, 1976. [68] Bistarelli S., Montanari U., Rossi F. Semiring-based constraint solving and optimization // Journal of the ACM. 1997. 44. P. 201­236.




143

[69] Bistarelli S., Montanari U., Rossi F. Semiring-based Constraint Logic Programming // Pro c. IJCAI97. Morgan Kaufman, 1997. [70] Semiring-based CSPs and valued CSPs: Frameworks, prop erties and comparison / S. Bistarelli [et al.] // Constraints. 1999. V. 4. P. 199­240. [71] Bitner J. R., Reingold E. M. Backtrack programming techniques // Communications of the Asso ciation for Computing Machinery. 1975. 18 (11). P. 651­656. [72] Blanco J. J., Khatib L. Course scheduling as a constraint satisfaction problem // Pro c. PACT98, 1998. [73] Bliek C., Neveu B., Tromb ettoni G. Using graph decomp osition techniques for solving continuous CSPs // Pro c. 4th Int. Conf. on Principles and Practice of Constraint Programming (CP98), Springer-Verlag, LNCS 1520, 1998. P. 102­116. [74] Blum A., Furst M. Fast planning through planning graph analysis // Artificial Intelligence. 1997. V. 90. P. 281­300. [75] Bo dirsky M., Ne etil J. Constraint satisfaction with countable sr homogeneous templates // Journal of Logic and Computation. 2006. V. 16. P. 359­373. [76] B¨hler E., Hemaspaandra E., Reith S., Vollmer H. The complexity o of Bo olean constraint isomorphism // STACS 2004 (Montp ellier, 2004), LNCS 2996. Berlin: Springer, 2004. P. 164­175. [77] Quantified constraints: Algorithms and complexity / F. B¨rner [et o al.] // Computer Science Logic (Vienna, 2003), Lecture Notes in Comput. Sci. 2803, Berlin: Springer, 2003. P. 58­70. [78] Borning A. The programming language asp ects of thinglab, a constraint oriented simulation lab oratory // ACM Transaction on Programming Languages and Systems. 1981. V. 3 (4). P. 353­387. [79] Borning A., Maher M., Martindale A., Wilson M. Constraint hierarchies and logic programming // Pro c. 6th International Conference on Logic Programming / M. Martelli, G. Levi (eds.). Cambridge: MIT Press, 1989. P. 149­164. [80] Borning A., Freeman-Benson B. N. The OTI constraint solver: a constraint library for constructing graphical user interfaces


144

. .

// Pro ceedings 1st Int. Conference on Principles and Practice of Constraint Programming (CP95). Springer-Verlag, LNCS 976, 1995. [81] Brailsford S. C., Potts C. N., Smith B. M. Constraint satisfaction problems: Algorithms and applications // Europ ean Journal of Op erational Research. 1999. V. 119. P. 557­581. [82] Brelaz D. New metho ds to color the vertices of a graph // Communications of the Asso ciation for Computing Machinery. 1979. 22 (4). P. 251­256. [83] Bro dsky A. Constraint databases: Promising technology or just intellectual exercise? // Constraints: An International Journal. 1997. V. 2. P. 35­44. [84] Bro dsky A., Jaffar J., Maher M. Toward practical query evaluation for constraint databases // Constraints: An International Journal, 1997. V. 2. P. 279­304. [85] Bro oke A., Kendrick D., Meeraus A. GAMS: A Users' Guide. Danvers: The Scientific Press, 1988. [86] Bruyno oghe M. Solving combinatorial search problems by intelligent backtracking // Inform. Pro cess. Lett. 1981. V. 12. P. 36­39. [87] Bruyno oghe M. Graph Coloring and Constraint Satisfaction. Technical Rep ort CW- 44. Kathioleke Universiteit Leuven: Department Computerwtenschapp en, 1985. [88] Bruyno oghe M. Enhancing a search algorithm to p erform intelligent backtracking // Theory Pract. Log. Program. 2004. V. 4. P. 371­380. [89] Bulatov A., Dalmau V. Mal'tsev constraints are tractable // SIAM J. on Computing. 2006. V. 36 (1). P. 16­27. [90] Bulatov A., Krokhin A., Jeavons P. Classifying the complexity of constraints using finite algebras // SIAM Journal on Computing. 2005. V. 34 (3). P. 720­742. [91] Bulatov A., Krokhin A., Jeavons P. The complexity of maximal constraint languages // Pro ceedings 33rd ACM Symp osium on Theory of Computing (STOC'01), 2001. P. 667­674.




145

[92] Bulatov A. Mal'tsev Constraints are Tractable. Technical Rep ort PRG­02­05, Computing Lab oratory, Oxford University, 2002. [93] Bulatov A., Jeavons P. G. Tractable Constraints Closed under a Binary Op eration. Technical Rep ort PRG­TR­12­00. Oxford, University of Oxford, Computing Lab oratory, 2002. [94] Bulatov A. Tractable conservative constraint satisfaction problems // Pro ceedings of the 18th Annual IEEE Simp osium on Logic in Computer Science, (LICS'03), 2003. P. 321­330. [95] Bulatov A., Dalmau V. Towards a dichotomy theorem for the counting constraint satisfaction problem // Pro ceedings 44rd IEEE Symp osium on Foundations of Computer Science, FOCS'03, Boston, 2003. P. 562­571. [96] Bulatov A., Dalmau V. A Simple Algorithm for Mal'tsev Constraints // SIAM J. Comput. 2006. V. 36. P. 16­27. [97] Buscemi M. G., Montanari U. A survey of constraint-based programming paradigms // Computer Science Review. 2008. V. 2. P. 137­141. [98] Cab on B., de Givry S., Verfaille G. Anytime lower b ounds for constraint violation minimization problems // Pro c. 4th Int. Conf. on Principles and Practice of Constraint Programming (CP98). Springer-Verlag, LNCS 1520, 1998. [99] Carlsson M., Widen J. SICStus Prolog User's Manual. Technical rep ort, Swedish Institute of Computer Science (SICS), 1999. on-line version at http://www.sics.se/sicstus/ ( 07.08.2010). [100] Carro M., Hermenegildo M. Some design issues in the visualization of constraint program execution // Pro c. Joint Conference on Declarative Programming (AGP'98), 1998. [101] Caseau Y., Laburthe F. Improved CLP scheduling with task intervals // Pro ceedings of the Eleventh International Conference on Logic Programming. Santa Margherita Ligure, 1994. P. 369­383. [102] Chan P., Heus K., Veil G. Nurse scheduling with global constraints in CHIP: Gymnaste // Pro c. PACT98, 1998. [103] Chan P. La planification du p ersonnel: acteurs, actions et termes multiples p our une planification op erationelle des p ersonnes.


146

. .

[104]

[105]

[106]

[107]

[108]

[109] [110]

[111]

[112]

PhD thesis, Universite Joseph Fourier, Grenoble 1. TIMC-IMAG, Octob er 2002. Cheeseman P., Kanefsky B., Taylor W. Where the really hard problems are // Pro ceedings of the Twelfth International Joint Conference on Artificial Intelligence (IJCAI-91). Morgan Kaufmann, 1991. P. 331­337. Chew T., David J.-M. A constraint-based spreadsheet for co op erative pro duction planning // Pro c. AAAI SIGMAN workshop on knowledge-based pro duction planning, scheduling and control, 1992. Chmeiss A., Jegou P. Path-consistency: when space misses time // Pro ceedings of the 13th National Conference on Artificial Intelligence. Portland, 1996. P. 196­201. Chow K. P., Perrett M. Airp ort counter allo cation using constraint logic programming // Pro c. Third International Conference on Constraint Technology (PACT97). London, 1997. Stand allo cation with constraint technologies at Chek Lap Kok international airp ort / A. H. W. Chun [et al.] // Pro c. The First International Conference and Exhibition on The Practical Application of Constraint Technologies and Logic Programming PACLP99 (19­21 April 1999), Commonwealth Conference and Events Centre, London, 1999. P. 131­136. Co dognet P., Diaz D. Compiling constraints in clp(fd) // Journal of Logic Programming. 1996. V. 27. P. 185­226. Cohen D. A., Gyssens M., Jeavons P. D. Derivation of constraints and database relations // Pro ceedings 2nd Int. Conference on Principles and Practice of Constraint Programming (CP96). Springer-Verlag, LNCS 1118, 1996. P. 134­148. Cohen D. A., Jeavons P., Koubarakis M. Tractable disjunctive constraints. // Pro c. 3rd Int. Conf. on Principles and Practice of Constraint Programming (CP97). Springer-Verlag, LNCS 1330, 1997. P. 478­490. Cohen D. A., Jeavons P. G., Jonsson P., Koubarakis M. Building tractable disjunctive constraints // Journal of the ACM. 2000. V. 47. P. 826­853.




147

[113] Cohen D., Jeavons P., Gault R. New tractable constraint classes from old // Exploring Artificial intelligence in the New Millennium / G. Lakemeyer, B. Neb el (eds.). San Francisco: Morgan Kaufmann Publishers, 2003. P. 331­354. [114] Cohen D. A., Jeavons P. D. The complexity of constraint languages. // Handb o ok of Constraint Programming, chapter 8. / F. Rossi, P. van Beek, T. Walsh (eds.). Elsevier, 2006. [115] Cohen D. A., Jeavons P. D., Gyssens M. A unified theory of structural tractability for constraint satisfaction problems // Journal of Computer and System Sciences. 2008. V. 74. P. 721­743. http://www.comlab.ox.ac.uk/activities/constraints/publications/ /JCSSspreadcut.p df ( 07.08.2010) [116] Cohen J. Logic Programming and Constraint Logic Programming // Computer Science Handb o ok / editor-in-chief A. B. Tucker. 2nd ed. Chapman & Hall/CRC, 2004. Chapter 93. [117] Collavizza H., Delob el F., Rueher M. A note on partial consistency over continuous domains // Pro c. 4th Int. Conf. on Principles and Practice of Constraint Programming (CP98). Springer-Verlag, LNCS 1520, 1998. P. 147­161. [118] Collignon C. Gestion optimisee de ressources humaines p our l'audiovisuel // Pro c. CHIP users' club, 1996. [119] Colmerauer A. Op ening the Prolog-I I I universe // BYTE magazine. 1987. V. 12. P. 177­182. [120] Colmerauer A. An intro duction to Prolog-I I I // Communication of the ACM. 1990. V. 33. P. 69­90. [121] Co op er M. C., Cohen D. A., Jeavons P. G. Characterising tractable constraints // Artificial Intelligence. 1994. V. 65. P. 347­361. [122] Co op er M. C., Jeavons P. D., Salamon A. Z. Hybrid tractable CSPs which generalize tree structure // Pro ceedings of the 18th Europ ean Conference on Artificial Intelligence (ECAI 2008) / M. Ghallab [et al.] eds, (July 21­25, Patras, Greece). Vol. 178 of Frontiers in Artificial Intelligence and Applications. IOS Press, 2008. P. 530­534. http://www.gaon.net/andras/academic/cjsecai2008.p df ( 07.08.2010)


148

. .

[123] COSYTEC, CHIP C library. COSYTEC SA, Parc Club Orsay Universite, 1995. [124] Constraint-based Maintenance Scheduling on an Electric PowerDistribution Network / T. Creemers [et al.] // Pro c. of the 3rd International Conference and Exhibition on Practical Applications of Prolog. Paris: Alinmead Software Ltd. April, 1995. P. 135­144. [125] Creignou N., Khanna S., Sudan M. Complexity Classification of Bo olean Constraint Satisfaction Problems, vol. 7 of SIAM Monographs on Discrete Mathematics and Applications. Philadelphia: SIAM, 2001. [126] Dalmau V. A new tractable class of constraint satisfaction problems // Annals of Mathematics and Artificial Intelligence. 2005. V. 44 (1­2). P. 61­85. [127] Constraint logic programming and integer programming approaches and their collab oration in solving an assignment scheduling problem / K. Darby-Dowman [et al.] // Constraints: An International Journal. 1997. V. 1. P. 245­264. [128] Davis M., Putnam H. A computing pro cedure for quantification theory. // Journal of the ACM. 1960. V. 7. P. 201­215. [129] de Bo er F., Gabbrielli M., Meo M. C. Semantics and expressive p ower of a timed concurrent constraint language // Pro c. Third Int'l Conf. on Principles and Practice of Constraint Programming (CP 97) / G. Smolka (ed.). LNCS 1330. Berlin: Springer-Verlag, 1997. P. 47­61. [130] de Kleer J. A comparison of ATMS and CSP techniques // Pro ceedings of the Eleventh International Joint Conference on Artificial Intelligence (IJCAI-89). Vol. 1. Detroit: Morgan Kaufmann, 1989. P. 290­296. [131] Dechter R. A Constraint-Network Approach to Truth-Maintenance. Technical Rep ort R-80. Cognitive Systems Lab oratory, University of California, Computer Science Department, 1987. [132] Dechter R., Dechter A. Belief maintenance in dynamic constraint networks // Pro ceedings of The 7th National Conference on Artificial Intelligence. St Paul, Minnesota, 1988. P. 37­42.




149

[133] Dechter R. Enhancement schemes for constraint pro cessing: Backjumping, learning and cutset decomp osition // Artificial Intelligence. 1990. V. 41. P. 273­312. [134] Dechter R. On the expressiveness of networks with hidden variables // Pro ceedings of the Eighth National Conference on Artificial Intelligence (AAAI­90). Boston: MIT Press, 1990. P. 379­385. [135] Dechter R. Constraint networks // Encyclop edia of Artificial Intelligence (2nd edition) / S. Shapiro (ed.). New York: Wiley and Sons, 1992. P. 276­285. [136] Dechter R. From lo cal to global consistency // Artificial Intelligence. 1992. V. 55. P. 87­107. [137] Dechter R. Bucket elimination: a unifying framework for pro cessing hard and soft constraints // Constraints. 1997. V. 2. P. 51­55. [138] Dechter R., Frost D. Backtracking satisfaction problems. Tech.rep., Department of Information and http://www.ics.uci.edu/ csp/r56-back 07.08.2010) algorithms for constraint University of California, Computer Science, 1999. tracking.p df ( -

[139] Dechter R., Meiri I. Exp erimental evaluation of prepro cessing techniques in constraint satisfaction problems // Artificial Intelligence. 1994. V. 68. P. 211­241. [140] Dechter R., Pearl J. Network-based heuristics for constraintsatisfaction problems // Artificial Intelligence. 1987. 34 (1). P. 1­38. [141] Dechter R., Pearl J. Tree clustering for constraint networks // Artificial Intelligence. 1989. 38 (3). P. 353­366. [142] Dechter R. Constraint pro cessing. San Francisco: Morgan Kaufmann, 2003. [143] De Givry S., Verfaille G., Schiex T. Bounding the optimum of constraint optimization problems // Pro c. CP97 / G. Smolka (ed.). Springer-Verlag, LNCS 1330, 1997. P. 405­419. [144] The mo delling language Zinc / M. G. de la Banda [et al.] // Principles and Practice of Constraint Programming CP 2006. LNCS 4204. Springer, 2006. P. 700­705.


150

. .

[145] To the Gates of HAL: a HAL tutorial / G. M. de la Banda // 6th International Conference on Functional and Logic Programming (FLOPS), Japan, 2002. [146] Denecke K., Wismath S. L. Universal Algebra and Applications in Theoretical Computer Science. Chapman and Hall/CRC Press, 2002. [147] An overview of HAL / B. Demo en [et al.] // International Conference on Principles and Practice of Constraint Programming, CP99. Alexandria, 1999. P. 174­188. [148] Deville Y., Jansenn M., Van Hentenryck P. Consistency techniques in ordinary differential equations // Pro c. 4th Int. Conf. on Principles and Practice of Constraint Programming (CP98), LNCS 1520. Springer-Verlag, 1998. P. 162­176. [149] The constraint logic programming language CHIP / M. Dincbas [et al.] // Pro c. International Conference on Fifth Generation Computer Systems (FGCS). Berlin Heidelb erg New York: Springer, 1988. P. 693­702. [150] Applications of CHIP to industrial and engineering problems / M. Dincbas [et al.] // First International Conference on Industrial and Engineering Applications of Artificial Intelligence and Exp ert Systems, Tullahoma, Tennessee, 1988. P. 885­892. [151] Dincbas M., Simonis H. Apache a constraint based, automated stand allo cation system // Pro c. of Advanced Software technology in Air Transp ort (ASTAIR'91). London, UK: Royal Aeronautical So ciety, 1991. P. 267­282. [152] Doyle J. A truth maintenance system // Artificial Intelligence. 1979. 12 (3). P. 231­272. [153] Dresse A. A constraint programming library dedicated to timetabling // Pro c. ILOG User-group meeting, 1995. [154] Dub ois D., Fargier H., Prade H. The calculus of fuzzy restrictions as a basis for flexible constraint satisfaction // Pro c. IEEE International Conference on Fuzzy Systems. IEEE, 1993. P. 1131­1136. [155] Dub os A., Du Jeu A. Application EPPER planification des ageents roulaants // Pro c. CHIP users' club, 1996.




151

[156] Dunkin N., Allen S. M. Frequency assignment problems: Representations and solutions. Technical Rep ort CSD­TR­97­14. Royal Holloway: University of London, 1997. [157] Towards High Order Constraint Representations for the Frequency Assignment Problem / N. W. Dunkin [et al.]. Technical Rep ort CSD­TR­98­05, Royal Holloway, University of London, June 1998. ftp://ftp.cs.rhul.ac.uk/pub/constraints/CSD-TR-9805.ps ( 07.08.2010) [158] The ECLiPSe Library Manual Release 5.0. http://www.win.tue.nl/ /~setalle/lp/eclipse-do c/libman/libman.html, 2000 ( 07.08.2010) [159] Even S. Graph Algorithms. Potomac: Computer Science Press, 1979. [160] Fargier H., Lang J., Schiex T. Selecting preferred solutions in fuzzy constraint satisfaction problems // Pro c. 1st Europ ean Ccongress on Fuzzy and Intelligent Technologies (EUFIT), 1993. [161] Feder T., Vardi M. Y. The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory // SIAM Journal of Computing. 1998. V. 28 (1). P. 57­104. [162] Fikes R. A heuristic program for solving problems stated as nondeterministic pro cedures. Ph.D. dissertation, Comput. Sci. Dept., Carnegie-Mellon Univ. Pittsburgh, 1968. [163] Filkhorn T., Schneider H.-A., Scholz A., Strasser A., Warkentin P. SVE system verification environment. Technical rep ort, Siemens AG, Technical rep ort SVE, ZFE BT SE, 1995. [164] Constraint logic programming for the crew rostering problem / F. Fo cacci [et al.] // Pro c. PACT97, 1997. [165] Efficient graph automorphism by vertex partitioning / G. Fowler [et al.] // Artificial Intelligence. 1983. V. 21. P. 245­269. [166] Fox M. S. Constraint-Directed Search: A Case Study of Job-Shop Scheduling. Pitman: Morgan Kaufmann, 1987. [167] Freuder E. C. Synthesizing constraint expressions // Communications of the Asso ciation for Computing Machinery. 1978. 21 (11). P. 958­966.


152

. .

[168] Freuder E. C. A sufficient condition for backtrack-free search // Journal of the ACM. 1982. 29 (1). P. 24­32. [169] Freuder E. C. A sufficient condition for backtrack-b ounded search // Journal of the ACM. 1985. 32 (4). P. 755­761. [170] Freuder E. C. Backtrack-free and backtrack-b ounded search // Search in Artificial Intelligence / L. Kanal, V. Kumar (eds.). Springer-Verlag, 1988. P. 343­369. [171] Freuder E. C., Mackworth A. K. Constraint satisfaction: An emerging paradigm // Foundations of Artificial Intelligence. 2006. V. 2. P. 13­27. [172] Freuder E. C., Wallace R. J. Partial constraint satisfaction // Artificial Intelligence. 1992. V. 58. P. 21­70. [173] Freuder E. C., Wallace R. J. Suggestion strategies for constraintbased matchmaker agents // Pro c. 4th Int. Conf. on Principles and Practice of Constraint Programming (CP98). Springer-Verlag, LNCS 1520, 1998. [174] Fromherz M., Gupta V., Saraswat V. Mo del-based computing: constructing constraint-based software for electro-mechanical systems // Pro c. Conf. on Practical Applications of Constraint Technology (PACT95). Paris, 1995. P. 63­66. [175] Fruhwirth T. Constraint simplification rules // Constraint ¨ Programming: Basics and Trends / A. Po delski, ed. SpringerVerlag, LNCS 910, 1995. [176] Fruhwirth T., Ab dennadher ¨ Programming. Springer, 2003. S. Essentials of Constraint

[177] Fruhwirth T., Brisset P. Optimal planning of digital cordless ¨ telecommunication systems // Pro c. PACT97. 1997. [178] Fuchs N., Schwitter R. Attempto controlled English (ACE) // Pro c. of 1st International Workshop on Controlled Language. 1996. [179] Gaschnig J. A constraint satisfaction metho d for inference making // Pro ceedings Twelfth Annual Allerton Conference on Circuit and System Theory. Illinois, Monticello, 1974. P. 866­874. [180] Gaschnig J. A general backtrack algorithm that eliminates most redundant tests // Pro ceedings of the Fifth International Joint




153

Conference on Artificial Intelligence (IJCAI­77). Cambridge, 1977. P. 457. [181] Gaschnig J. Performance measurement and analysis of certain search algorithms. Technical rep ort CMU­CS­79­124. CarnegieMellon University, Computer Science Department, 1979. [182] Extending CLP(FD) with interactive data acquisition for 3D visual ob ject recognition / M. Gavanelli [et al.] // Pro c. PACLP99. 1999. [183] Geco de: Generic Constraint Development Environment. http://www.geco de.org ( 07.08.2010). [184] Georget Y., Co dognet P., Rossi F. Constraint retraction in clp(fd): Formal framework and p erformance results // Constraints: An International Journal. 1999. V. 4. [185] Georget Y., Co dognet P. Compiling semiring-based constraints with clp(fd,s) // Pro c. CP98 / M. Maher, J-F. Puget (eds.) SpringerVerlag, LNCS 1520, 1998. [186] Gervet C. Conjunto: Constraint logic programming with finite set domains // Logic Programming. Pro c. of the 1994 International Symp osium / M. Bruyno oghe, ed. Cambridge: The MIT Press, 1994. P. 339­358. [187] Gervet C., Caseau Y., Montaut D. On refining ill-defined constraint problems: A case study in iterative prototyping // Pro c. PACLP99, 1999. [188] Ginsb erg M. L. Essentials of Artificial Intelligence. San Mateo: Morgan Kaufmann, 1993. [189] Ginsb erg M. L. Dynamic Backtracking // Journal of Artificial Intelligence Research. 1993. V. 1. P. 25­46. [190] Ginsb erg M. L., McAllester D. A. GSAT and dynamic backtracking // Pro ceedings of The 4th International Conference on Principles of Knowledge Representation and Reasoning, 1994. [191] Glaisner F., Richard L.-M. FORWARD-C: A refinery scheduling system // Pro c. PACT97. 1997. [192] Goldin D. Q., Kanellakis P. Constraint query algebras // Constraints: An International Journal. 1996. V. 1. P. 45­84.


154

. .

[193] Goltz H.-J., Matke D. Combined interactive and automatic timetabling // Pro c. PACLP99. 1999. [194] Gomes C. P. Artificial intelligence and op erations research: challenges and opp ortunities in planning and scheduling // Knowl. Eng. Rev. 2000. V. 15. P. 1­10. [195] Gottlob G., Leone N., Scarcello F. A comparison of structural CSP decomp osition metho ds // Pro ceedings of the Sixteenth International Joint Conference on Artificial Intelligence (IJCAI­99). Sto ckholm: Morgan Kaufmann, 1999. P. 394­399. [196] Gottlob G., Leone N., Scarcello F. Hyp ertree decomp ositions and tractable queries // Pro ceedings of the 18th ACM International Symp osium on Principles of Database Systems. Philadelphia: Asso ciation for Computing Machinery, 1999. P. 21­32. [197] Gottlob G., Leone N., Scarcello F. Hyp ertree decomp osition and tractable queries // Journal of Computer and System Sciences. 2002. V. 64 (3). P. 579­627. [198] Grohe M. The structure of tractable constraint satisfaction problems // Pro ceedings of the 31st Symp osium on Mathematical Foundations of Computer Science, LNCS 4162. Springer-Verlag, 2006. P. 58­72. [199] Dedale: A spatial constraint database / S. Grumbach [et al.] // Pro c. Intl. Workshop on Database Programming Languages (DBPL'97). Estes Park, Colorado, USA, 1994. [200] Gu J. Parallel Algorithms and Architectures for Very Fast AI Search. Ph. D. thesis. University of Utah, 1989. [201] Gyssens M., Jeavons P. G., Cohen D. A. Decomp osing constraint satisfaction problems using database techniques // Artificial Intelligence. 1994. V. 66. P. 57­89. [202] Han C., Lee C. Comments on Mohr and Henderson's path consistency algorithm // Artificial Intelligence. 1988. V. 36. P. 125­130. [203] Haralick R. M., Elliot G. L. Increasing tree search efficiency for constraint satisfaction problems // Artificial Intelligence. 1980. V. 14 (3). P. 263­313. [204] Programming languages for distributed applications / S. Haridi [et al.] // New Generation Computing. 1998. V. 16. P. 223­261.




155

[205] Haridi S., Janson S. Kernel Andorra Prolog and its computational mo del // Pro c. ICLP90. MIT Press, 1990. [206] Harvey W., Ginsb erg M. Limited discrepancy search // Pro c. IJCAI95. 1995. [207] Henz M., Smolka G., Wurtz J. Oz a programming language for multiagent systems // 13th International Joint Conference on Artificial Intelligence / Ruzena Ba jcsy, ed. V. 1. Morgan Kaufmann Publishers, 1993. P. 404­409. [208] Hermenegildo M. and the CLIP group. Some metho dological issues in the design of CIAO, a generic, parallel concurrent constraint system // Pro ceedings of the Second International Workshop on Principles and Practice of Constraint Programming, May 02­04, 1994. Springer-Verlag, LNCS 874, 1994. P. 123­133. [209] Hicks I. V., Koster A. M. C. A., Kolotoglu E. Branch and tree decomp osition techniques for discrete optimization // Tutorials in Op erations Research. New Orleans: INFORMS, 2005. P. 1­29. http://ise.tamu.edu/p eople/faculty/Hicks/bwtw.p df ( 07.08.2010). [210] Hobby D., McKenzie R. N. The Structure of Finite Algebras, volume 76 of Contemp orary Mathematics. Providence: American Mathematical So ciety, 1988. [211] Ho oker J. N., Yan H. Verifying logic circuits by Benders decomp osition // Principles and Practice of Constraint Programming / V. A. Saraswat, P. van Hentenryck (eds.) Cambridge: MIT Press, 1994. [212] Ho oker J. N., Ottosson G., Thorsteinsson E. S., Kim H.-J. A scheme for unifying optimization and constraint satisfaction metho ds // The Knowledge Engineering Review. 2000. V. 15, N. 1. P. 11­30. [213] Ho oker J. N. Logic-Based Metho ds for Optimization: Combining Optimization and Constraint Satisfaction. New York: Wiley, 2000. [214] Hower W. Constraint satisfaction Algorithms and complexity analysis // Information Pro cessing Letters. 1995. Vol. 55 (3). P. 171­178.


156

. .

[215] Hyvonen E. Interval constraints spreadsheets for financial planning // Pro c. 1st Int. Conf. on Artificial Intelligence Applications on Wall Street. IEEE Computer So ciety Press, 1991. [216] ILOG SOLVER: Ob ject oriented constraint programming. ILOG SA, 12, Av. Raspail, BP 7, 94251 Gentilly cedex, France, 1995. [217] ILOG Scheduler. http://www.ilog.fr/pro ducts/scheduler/ [218] Istrate G. Counting, structure identification and maximum consistency for binary constraint satisfaction problems // Pro ceedings 3rd Int. Conference on Principles and Practice of Constraint Programming / G. Smolka (ed.) Springer-Verlag, LNCS 1330, 1997. P. 136­149. [219] Jackson D. Software Abstractions: Logic, Language, and Analysis. Cambridge: The MIT Press, 2006. [220] Jaffar J., Lassez J.L. Constraint logic programming // Pro c. 14th ACM Symp. Principles Programming Lang. POPL­87. Munich, ACM Press, 1987. P. 111­119. [221] Jaffar J., Maher M. J. Constraint logic programming: A survey // Journal of Logic Programming. 1994. V. 19. P. 503­581. [222] The CLP(R) Language and System / J. Jaffar // ACM Transactions on Programming Languages and Systems. 1992. V. 14. P. 339­395. [223] Jamp el M. (ed.) Over-Constrained Systems. Springer-Verlag, LNCS 1106, 1996. [224] Janson S. AKL A Multiparadigm Programming Language. PhD thesis, Uppsala Theses in Computer Science 19, Uppsala University, and SICS Dissertation Series 14, 1994. [225] Jeavons P. G. On the algebraic structure of combinatorial problems // Theoretical Computer Science. 1998. V. 200. P. 185­204. ftp://ftp.cs.rhul.ac.uk/pub/constraints/algebraic.ps ( 07.08.2010). [226] Jeavons P. G. Constructing constraints // Pro c. 4th Int. Conf. on Principles and Practice of Constraint Programming (CP98). Springer-Verlag, LNCS 1520, 1998. P. 2­16. ftp://ftp.cs.rhul.ac.uk/ /pub/constraints/constructing.ps ( 07.08.2010). [227] Jeavons P. G., Cohen D. A., Gyssens M. Closure prop erties of constraints // Journal of ACM. 1997. V. 44. P. 527­548.




157

[228] Jeavons P. G., Cohen D. A., Co op er M. C. Constraints, consistency and closure // Artificial Intelligence. 1998. V. 101. P. 251­265. ftp://ftp.cs.rhul.ac.uk/pub/constraints/conconclo.ps ( 07.08.2010). [229] Jeavons P. G., Cohen D. A. An algebraic characterization of tractable constraints // Pro c. of Computing and Combinatorics (COCOON'95). Springer-Verlag, LNCS 959, 1995. P. 633­642. [230] Jeavons P. G., Cohen D. A., Gyssens M. A unifying framework for tractable constraints // Pro c. 1st Int. Conf. on Principles and Practice of Constraint Programming (CP95), Springer-Verlag, LNCS 976, 1995. P. 276­291. [231] Jeavons P. G., Cohen D. A., Gyssens M. How to determine the expressive p ower of constraints // Constraints: An international Journal 1999. V. 4. P. 113­131. [232] Jeavons P. G., Cohen D. A., Gyssens M. A test for tractability // Pro c. 2nd Int. Conf. on Principles and Practice of Constraint Programming (CP96). Springer-Verlag, LNCS 1118, 1996. P. 267­281. [233] Jeavons P. G., Co op er M. C. Tractable constraints on ordered domains // Artificial Intelligence. 1995. 79 (2). P. 327­339. [234] Jonsson P., Krokhin A. Recognizing frozen variables in constraint satisfaction problems // Theoret. Comput. Sci. 2004. V. 329 (1­3). P. 93­113. [235] Kam R. W. L., Lee J. H. M. Fuzzifying the constraint hierarchies framework // Pro c. 4th Int. Conf. on Principles and Practice of Constraint Programming (CP98). Springer-Verlag, LNCS 1520, 1998. [236] Kanellakis P., Goldin D. Q. Constraint programming and database query languages // Pro c. Int. Symp. on Theoretical Asp ects of Computer Software. Springer-Verlag, LNCS 789, 1994. P. 96­120. [237] Kanellakis P., Kup er G., Revesz P. Constraint query languages // Journal of Computer and System Sciences. 1995. V. 51. P. 25­52. [238] Katsirelos G., Bacchus F. Generalized NoGo o ds in CSPs // Pro c. of 20th AAAI, 2005. P. 390­396. [239] Katsirelos G. Nogo o d Pro cessing in CSPs. Phd thesis. University of Toronto, 2008.


158

. .

[240] Kautz H., Selman B. Planning as Satisfiability // Pro ceedings of Europ ean Conference on Artificial Intelligence ECAI­92 (Vienna, 1992). Chichester: John Wiley and Sons, 1992. P. 359­363. [241] The approximability of constraint satisfaction problems / S. Khanna [et al.] // SIAM J. Comput. 2000. V. 30 (6). P. 1863­1920. [242] Estimating search tree size / P. Kilby [et al.] // Pro ceedings of AAAI­2006. 2006. P. 1014­1019. [243] Kirkpatrick S., Gelatt C. D., Vecchi M. P. Optimization by simulated annealing // Science. 1983. V. 220. P. 671­680. [244] Kirousis L., Kolaitis Ph. A dichotomy in the complexity of prop ositional circumscription // Logic in Computer Science (Boston, MA, 2001). IEEE Comput. So c., 2001. P. 71­80. [245] Knuth D. Estimating the efficiency of backtrack programs // Mathematics of Computation. 1975. V. 29 (129). P. 121­136. [246] Kokkoras F., Gregory S. D-WMS: Distributed workforce management using CLP // Pro c. 4th Int. Conference on the Practical Applications of Constraint Technology (PACT'98). London, UK, 25­27 March, 1998. P. 129­146. [247] Kolaitis P., Vardi M. Conjunctive-query containment and constraint satisfaction // Journal of Computer and System Sciences. 2000. V. 61. P. 302­332. [248] Kondrak G., van Beek P. A theoretical evaluation of selected backtracking algorithms // Artificial Intelligence. 1997. V. 89. P. 365­387. [249] Korf R. Improved limited discrepancy search // Pro ceedings of the 13th National Conference on Artificial Intelligence (AAAI­96) (Portland). 1996. P. 209­215. [250] Koubarakis M. Querying Temp oral Constraint Networks: A Unifying Approach // Applied Intelligence. 2002. V. 17. P. 297­311. [251] Krokhin A., Jeavons P., Jonsson P. Reasoning ab out temp oral relations: The tractable subalgebras of Allen's interval algebra // Journal of the ACM. 2003. V. 50. P. 591­640. [252] Krokhin A., Bulatov A., Jeavons P. Functions of multiple-valued logic and the complexity of constraint satisfaction: A short survey




159

// Pro ceedings 33rd IEEE International Symp osium on MultipleValued Logic (ISMVL 2003). IEEE Computer So ciety, 2003. P. 343­351. [253] Krokhin A., Bulatov A., Jeavons P. The complexity of constraint satisfaction: an algebraic approach // Structural Theory of Automata, Semigroups, and Universal Algebra, volume 207 of NATO Science Series I I: Math., Phys., Chem., Springer Verlag, 2005. P. 181­213. [254] Kuip ers B. Qualitative Reasoning: Mo deling and Simulation with Incomplete Knowledge. MIT Press, 1994. [255] Kumar V. Algorithms for constraint satisfaction problems: A survey // AI Magazine. 1992. 13 (1). P. 32­44. [256] Laburthe F., Caseau Y. SALSA: A language for search algorithms // Pro ceedings of the 4h International Conference on the Principles and Practice of Constraint Programming (CP'98) (Pisa, Italy), 1998. [257] Larrosa J., Morancho E., Niso D. On the practical applicability of bucket elimination: Still-life as a case study // Journal of Artificial Intelligence Research. 2005. V. 23. P. 421­440. [258] Lauriere J.-L. ALICE: A language and a program for stating and solving combinatorial problems // Artificial Intelligence. 1978. V. 10 (1). P. 29­127. [259] Leler Wm. Constraint Programming Languages, Their Sp ecification and Generation. Reading: Addison-Wesley, 1988. [260] Engineering dynamic scheduler for Work Manager / D. Lesaint [et al.] // BT Technology Journal. 1998. V. 16. P. 16­29. [261] Lloyd J. W. Foundations of Logic Programming. Berlin: Springer Verlag, 1987. [262] Mackworth A. K. Consistency in networks of relations // Artificial Intelligence. 1977. 8 (1). P. 99­118. [263] Mackworth A. K. Constraint satisfaction // Encyclop edia of Artificial Intelligence (second edition) / S. Shapiro (ed.) New York: Wiley, 1992. Vol. 1. P. 285­293.


160

. .

[264] Mackworth A. K. On reading sketch maps // Pro ceedings of the Fifth International Joint Conference on Artificial Intelligence Cambridge, 1977. P. 598­606. [265] Mackworth A. K., Freuder E. C. The complexity of some p olynomial network consistency algorithms for constraint satisfaction problems // Artificial Intelligence. 1985. V. 25 (1). P. 65­74. [266] Marriott K., Stuckey P. J. Programming with Constraints: An Intro duction. Cambridge: MIT Press, 1998. [267] Zinc 0.1: Language and libraries. Technical rep ort / K. Marriott [et al.] Monash University, 2006. [268] The design of the Zinc mo delling language / K. Marriott [et al.] // Constraints 2008. V. 13, N 3. P. 229­267. [269] Maximuck W., Reviakin M. A prototyp e of train schedule mo dule // Pro c. PACT98, 1998. [270] McAlo on K. Co op erating solvers: A progress rep ort // Pro c. PACLP99, 1999. [271] McAlo on K., Tretkoff C. 2LP: Linear programming and logic programming // Principles and Practice of Constraint Programming / V. Saraswat, P. Van Hentenryck (eds). MIT Press, 1995. P. 99­114. [272] McDermott D. A general framework for reason maintenance // Artificial Intelligence. 1991. V. 50. P. 289­329. [273] McGregor J. J. Relational consistency algorithms and their application in finding subgraph and graph isomorphisms // Information Sciences. 1979. V. 19 (3). P. 229­250. [274] McKenzie R. N., McNulty G. F., Taylor W. F. Algebras, Lattices and Varieties. Vol. I. California: Wadsworth and Bro oks, 1987. [275] Mehlhorn K., Thiel S. Faster algorithms for b ound-consistency of the sortedness and alldifferent constraint // Pro ceedings of the Sixth International Conference on Principles and Practice of Constraint Programming. Singap ore, 2000. P. 306­319. [276] Melzer S. Verification of parallel systems using constraint programming // Pro c. 3rd Int. Conf. on Principles and Practice of Constraint Programming (CP97). Springer-Verlag, LNCS 1330, 1997.




161

[277] Menzel W. Constraint satisfaction for robust parsing of sp oken language // Journal of Exp erimental and Theoretical Artificial Intelligence. 1998. V. 10. P. 77­89. [278] Meseguer P. Constraint satisfaction problems: an overview // AI Communications. 1989. V. 2. P. 3­17. [279] Meseguer P. Interleaved depth-first search // Pro ceedings of the 15th International Joint Conference on Artificial Intelligence (Nagoya, Japan), 1997. [280] Meyer auf 'm Hofe H. ConPlan/SIEDAplan, p ersonnel assignment as a problem of hierarchical constraint satisfaction // Pro c. PACT 97, 1997. P. 257­271. [281] Michel L., Van Hentenryck P. Lo calizer // Constraints. 2000. V. 5 (1/2). P. 43­84. [282] Miguel I., Shen Q. Extending qualitative mo delling for simulation of time-delayed b ehaviour // Pro ceedings of The 12th International Workshop on Qualitative Reasoning. Massachusetts, Cap e Co d, 1998. P. 161­166. [283] Miguel I., Shen Q. Solution techniques for constraint satisfaction problems: foundations // Artificial Intelligence Review. 2001. V. 15. P. 241­265. [284] Miguel I., Shen Q. Solution techniques for constraint satisfaction problems: advanced approaches // Artificial Intelligence Review. 2001. V. 15. P. 267­291. [285] Minimizing conflicts: A heuristic repair metho d for constraint satisfaction and scheduling problems / S. Minton [et al.] // Artificial Intelligence. 1992. 55 (1­3). P. 161­205. [286] Mitchell D. Hard problems for CSP algorithms // Pro ceedings of the AAAI National Conference, 1998. P. 398­405. [287] Mohr R., Henderson T. C. Arc and path consistency revisited // Artificial Intelligence. 1986. 28 (2). P. 225­233. [288] Mohr R., Masini G. Go o d old discrete relaxation // Pro ceedings of the 8th Europ ean Conference on Artificial Intelligence. Munchen, ¨ 1988. P. 651­656.


162

. .

[289] Montanari U. Networks of constraints: Fundamental prop erties and applications to picture pro cessing // Information Sciences. 1974. 7 (2). P. 95­132. [290] Montelius J., Ali K. A. M. An and/or-parallel implementation of AKL // New Generation Computing. 1996. V. 14. P. 31­52. [291] Moskewicz M., Madigan C., Zhao Y., Zhang L., Malik S. Chaff: Engineering an efficient sat solver / M. Moskewicz [et al.] // Pro c. of the Design Automation Conference (DAC), 2001. [292] http://www.mozart-oz.org/. The Mozart pro ject, 2008 ( 07.08.2010). [293] Nadel B. A. Constraint satisfaction algorithms // Comput. Intelligence. 1989. V. 5. P. 188­224. [294] Nadel B. A. Constraint satisfaction in Prolog: Complexity and theory-based heuristics // Information Sciences, An International Journal. 1995. V. 83. P. 113­131. [295] Neumaier A. Complete search in continuous global optimization and constraint satisfaction // Acta Numerica. Cambridge University Press, 2004. P. 271­369. [296] Le Pap e C., Baptiste P. A constraint programming library for preemptive and non-preemptive scheduling // Pro c. PACT97, 1997. [297] Le Pap e C., Baptiste P. Resource constraints for preemptive jobshop scheduling // Constraints: An International Journal, 1998. V. 3. P. 263­287. [298] Pareschi R. Work force management in telecommunications and b eyond telecommunications // Pro c. PACLP99, 1999. [299] Pachet F. Constraints and multimedia // Pro c. PACLP99, 1999. [300] Papadimitriou C. H. Addison-Wesley, 2005. Computational Complexity. Reading:

[301] Pearson J., Jeavons P. A survey of tractable constraint satisfaction problems. Technical rep ort CSD­TR­97­15. U. of London, Royal Holloway College, 1997. [302] Peirce C. S. Collected Pap ers / C. Hartshorne, P. Weiss (eds.), Vol. I I I. Harvard University Press, 1933.




163

[303] Perrett M. Using constraint logic programming techniques in container p ort planning // ICL Technical Journal. 1991. P. 537­545. [304] Perron L. Search pro cedures and parallelism in constraint programming // Pro ceedings of the 5th International Conference on the Principles and Practice of Constraint Programming (CP'99) (Alexandra), 1999. [305] Pesant G., Gendreau M., Rousseau J.-M. GENIUS-CP: a generic single-vehicle routing algorithm // Pro c. 3rd Int. Conf. on Principles and Practice of Constraint Programming (CP97). Springer-Verlag, LNCS 1330, 1997. [306] Poschel R., Kalunin L. A. Funktionen- und Relationenalgebren. ¨ z DVW, Berlin, 1979. [307] Le manuel de Prolog IV / F. Benhamou [et al.] Marseille: PrologIA, 1996. [308] Prosser P. A reactive scheduling agent // Pro ceedings of the 11th International Joint Conference on Artificial Intelligence IJCAI­89. Detroit, 1989. P. 1004­1009. [309] Prosser P. Hybrid algorithms for constraint satisfaction problems // Computational Intelligence. 1993. V. 9. P. 268­299. [310] Purvis L., Jeavons P. Constraint tractability theory and its application to the pro duct development pro cess for a constraintbased scheduler // Pro ceedings of 1st International Conference on The Practical Application of Constraint Technologies and Logic Programming, PACLP'99. Practical Applications Company, 1999. P. 63­79. [311] R´gin J. A filtering algorithm for constraints of difference in CSPs e // Pro ceedings of the Twelfth National Conference on Artificial Intelligence (AAAI­94). Seattle: AAAI Press, 1994. P. 362­367. [312] R´gin J. Generalized arc consistency for global cardinality e constraint // Pro ceedings of the Thirteenth National Conference on Artificial Intelligence. Portland, 1996. P. 209­215. [313] R´gin J. The symmetric alldiff constraint // Pro c. IJCAI99, 1999. e [314] Reith S., Vollmer H. Optimal satisfiability for prop ositional calculi and constraint satisfaction problems // Inform. and Comput. 2003. V. 186. P. 1­19.


164

. .

[315] Renker G., Ahriz H. Building mo dels through formal sp ecification // Pro c. of the First Int. Conf. on the Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. Springer, LNCS 3011, 2004. P. 395­401. [316] Revesz P. Z. Safe stratified Datalog with integer order programs // Pro ceedings of 1st Int. Conference on Principles and Practice of Constraint Programming (CP95). Springer-Verlag, LNCS 976, 1995. P. 154­169. [317] Revesz P. Z. Safe Datalog queries with linear constraints // Pro c. 4th Int. Conf. on Principles and Practice of Constraint Programming (CP98). Springer-Verlag, LNCS 1520, 1998. P. 355­369. [318] http://www.comp.rgu.ac.uk/staff/ha/ZCSP/ 07.08.2010). (

[319] Rit J. F. Propagating temp oral constraints for scheduling // Pro ceedings of the 5th National Conference on Artificial Intelligence. Philadelphia, 1986. P. 383­386. [320] Rob ertson N., Seymour P. D. Graph minors, ii. Algorithmic asp ects of tree-width // Journal of Algorithms. 1986. 7 (3). P. 309­322. [321] Ro dosek R., Wallace M. A generic mo del and hybrid algorithm for hoist scheduling probleems // Pro c. 4th Int. Conf. on Principles and Practice of Constraint Programming (CP98). Springer-Verlag, LNCS 1520, 1998. P. 385­399. [322] Rossi F. Constraint (logic) programming: A survey on research and applications // New Trends in Constraints / K. R. Apt [et al.] (eds.) Berlin: Springer, 1999. P. 40­74. [323] Rossi F., Petrie C., Dhar V. On the equivalence of constraint satisfaction problems. Technical Rep ort ACT­AI­222­89, MCC, Austin, Texas, 1989. [324] Rossi F., van Beek P., Walsh T. (eds.) Handb o ok Of Constraint Programming. Elsevier, 2006. [325] Rossi F., van Beek P., Walsh T. Chapter 4 Constraint Programming in Foundations of Artificial Intelligence. // Handb o ok of Knowledge Representation / F. van Harmelen, V. Lifschitz, B. Porter (eds.) 2008. V. 3. P. 181­211.




165

[326] Rossi F., Montanari U. Exact solution of networks of constraints using p erfect relaxation // Pro c. International Conference on Knowledge Representation (KR89). Morgan Kaufmann, 1989. [327] Rossi F., Sp erduti A. Learning solution preferences in constraint problems // Journal of Exp erimental and Theoretical Computer Science. 1998. V. 10. P. 103­116. [328] Ruttkay Zs. Fuzzy constraint satisfaction // Pro c. 3rd IEEE International Conference on Fuzzy Systems, 1994. P. 1263­1268. [329] Ruttkay Zs. Constraint satisfaction a survey // CWI Quarterly. 1998. V. 11. P. 163­214. [330] Sabin D., Freuder E. C. Contradicting conventional wisdom in constraint satisfaction // Pro ceedings of 11th Europ ean Conference on Artificial Intelligence (ECAI 94). Amsterdam: Wiley, 1994. P. 125­129. [331] Sam-Haroud D., Faltings B. Consistency techniques for continuous constraints // Constraints: An International Journal. 1996. V. 1. P. 85­118. [332] Schaefer T. J. The complexity of satisfiability problems // Pro ceedings 10th ACM Symp osium on Theory of Computing (STOC'78). 1978. P. 216­226. [333] Schiex T. Possibilistic constraint satisfaction problems, or how to handle soft constraints? // Pro c. 8th Conf. of Uncertainty in AI, 1992. P. 269­275. [334] Schiex T., Fargier H., Verfaille G. Valued constraint satisfaction problems: hard and easy problems // Pro c. IJCAI95. Morgan Kaufmann, 1995. P. 631­637. [335] Schulte C. Oz explorer: a visual constraint programming to ol // Pro ceedings of the 14th Int. Conf. on Logic programming. MIT Press, 1997. P. 286­300. [336] Schulte C. Programming constraint inference engines // Pro c. 3rd Int. Conf. on Principles and Practice of Constraint Programming (Schloss Hagenb erg, Linz, Austria, CP97). Springer-Verlag, LNCS 1330, 1997. P. 519­533. [337] Seidel R. A new metho d for solving constraint satisfaction problems // Pro ceedings of IJCAI­81. 1981. P. 338­342.


166

. .

[338] Sergiou K., Walsh T. The difference all-difference makes // Pro c. IJCAI99. 1999. [339] Spatial mo delling with geometric constraints / B. Seyb old [et al.] // Pro c. PACT97. 1997. [340] Shaw P. Using constraint programming and lo cal search metho ds to solve vehicle routing problems // Pro c. 4th Int. Conf. on Principles and Practice of Constraint Programming (CP98). Springer-Verlag, LNCS 1520, 1998. [341] Shen Q., Leitch R. Fuzzy Qualitative Simulation // IEEE Transactions on Systems. Man and Cyb ernetics. 1993. V. 23 (4). P. 1038­1061. [342] Shvetsov I., Kornienko V., Preis S. Interval spreadsheet for problems of financial planning // PACT'97. England, London, 1997. P. 373­385. [343] Schwalb E., Vila L. Temp oral Constraints: A Survey // Constraints. 1998. V. 3. P. 129­149. [344] Simonis H. Visual CHIP a visual language for defining constraint programs // CCL I I workshop. 1997. [345] Simonis H., Aggoun A. Search tree debugging. Technical rep ort, COSYTEC SA, 1997. [346] Simonis H., Cornelissens T. Mo delling pro ducer/consumer constraints // Pro ceedings 1st Int. Conference on Principles and Practice of Constraint Programming (CP95). Springer-Verlag, LNCS 976, 1995. P. 449­462. [347] Simonis H. Application development with the CHIP system // Pro ceedings of the ESPRIT WG CONTESSA Workshop on Constraint Databases and Applications (Septemb er 08­09, 1995) / G. M. Kup er, M. Wallace (eds.) LNCS 1034. London: SpringerVerlag, 1996. P. 1­21. [348] Simonis H. Building industrial applications with constraint programming // Constraints in computational logics: theory and applications. New York: Springer-Verlag, 2001. P. 271­309. [349] Simonis H. Mo dels for global constraint applications // Constraints. 2007. V. 12. P. 63­92.




167

[350] Simonis H., Charlier P. Cobra a system for train crew scheduling // Pro c. DIMACS workshop on constraint programming and large scale combinatorial optimization. 1998. [351] Simons R. V. Mathematical programming mo deling using MGG // IMA Journal of Mathematics in Management. 1987. V. 1. P. 267­276. [352] Smedback G., Carro M., Hermenegildo M. Interfacing Prolog and VRML and its applications to constraint visualization // The Practical Application of Constraint Technologies and Logic Programming (PACLP99). 1999. P. 453­471. [353] Smolka G. A foundation for higher-order concurrent constraint programming // 1st International Conference on Constraints in Computational Logics / Jean-Pierre Jouannaud (ed.) LNCS 845. Berlin: Springer-Verlag, 1994. P. 50­72. [354] Sosic R., Gu J. Efficient lo cal search with conflict minimization: A case study of the -queens problem // IEEE Transactions on Knowledge and Data Engineering. 1994. 6 (5). P. 661­668. [355] Stallman R. M., Sussman G. J. Forward reasoning and dep endencydirected backtracking in a system for computer-aided circuit analysis // Artificial Intelligence. 1977. 9 (2). P. 135­196. [356] Sutherland I. Sketchpad: A man-machine graphical communication system // Pro ceedings of the Spring Joint Computer Conference. IFIPS, 1963. P. 329­346. [357] Resource allo cation in distributed factory scheduling / K. P. Sycara [et al.] // IEEE Exp ert. 1991. V. 6. P. 29­40. [358] Szendrei A. Clones in Universal Algebra. Vol. 99 of Seminaires de Mathematiques Sup erieures. University of Montreal, 1986. [359] A constraint-based approach for visualization and animation / S. Takahashi [et al.] // Constraints: An International Journal. 1998. V. 3. P. 61­86. [360] Tamassia R. Constraints in graph drawing algorithms // Constraints: An International Journal. 1998. V. 3. P. 87­120. [361] Tarjan R. E., Yannakakis M. Simple linear-time algorithms to test chordality of graphs, test acyclicity of hyp ergraphs, and selectively


168

. .

reduce acyclic hyp ergraphs // SIAM Journal of Computing. 1984. V. 13. P. 566­579. [362] Toman D. Memoing evaluation for constraint extensions of Datalog // Constraints: An International Journal. 1997. V. 2. P. 337­360. [363] Tsang E. P. K. The consistent lab eling problem in temp oral reasoning // Pro ceedings of the 6th National Conference on Artificial Intelligence. 1987. P. 251­255. [364] Tsang E. Foundations of Constraint Satisfaction. New York: Academic Press, 1993. [365] A computer aided constraint programming system / E. Tsang [et al.] // Pro c. PACLP99. 1999. [366] Ullman J. R. An algorithm for subgraph isomorphism // Journal of the ACM. 1976. V. 23. P. 31­42. [367] Van Beek P. Reasoning ab out qualitative temp oral information // Artificial Intelligence. 1992. V. 58. P. 297­326. [368] Van Hentenryck P. Constraint Satisfaction in Logic Programming. Cambridge: MIT Press, 1989. [369] Van Hentenryck P., Deville Y., Teng C. M. A generic arcconsistency algorithm and its sp ecializations // Artificial Intelligence. 1992. V. 57. P. 291­321. [370] Van Hentenryck P. Helios: a mo deling language for global optimization // Pro ceedings PACT'96. 1996. P. 317­335. [371] Van Hentenryck P., Michel L., Deville Y. Numerica: A Mo deling Language for Global Optimization. Cambridge: MIT Press, 1997. [372] Van Hentenryck P., Saraswat V. (eds.) Sp ecial issue on Strategic Directions on Constraint Programming // Constraints: An International Journal. 1997. V. 2, N 1. [373] Van Hentenryck P. Visual solver: A mo deling language for constraint programming // Pro c. 3rd Int. Conf. on Principles and Practice of Constraint Programming (CP97). Springer-Verlag, LNCS 1330, 1997. [374] Van Hentenryck P. The OPL Optimization Language. MIT Press, 1999. Programming




169

[375] Van Hentenryck P., Perron L., Puget J.-F. Search and strategies in OPL // ACM Transactions on Computational Logic. 2000. V. 1. P. 1­36. [376] Van Hentenryck P., Michel L. Constraint-Based Lo cal Search. Cambridge: MIT Press, 2005. [377] Wallace M. Practical applications of constraint programming // Constraints: An International Journal. 1996. V. 1. P. 139­168. [378] Wallace M., Novello S., Schimpf J. Eclipse: A platform for constraint logic programming. Technical rep ort. IC-Parc, London, Imp erial College, 1997. [379] Wallace M., Novello S., Schimpf J. Eclipse a platform for constraint programming // ICL Systems Journal. 1997. V. 12 (1). P. 159­200. [380] Wallace R. J., Freuder E. C. Stable solutions for dynamic constraint satisfaction problems // Pro c. 4th Int. Conf. on Principles and Practice of Constraint Programming (CP98). Springer-Verlag, LNCS 1520, 1998. [381] Walsh T. Depth-b ounded discrepancy search // Pro ceedings of the 15th International Joint Conference on Artificial Intelligence. Nagoya, Japan, 1997. [382] Walsh T. Reformulating prop ositional satisfiability as constraint satisfaction // Pro ceedings of the 4th International Symp osium on Abstraction, Reformulation, and Approximation. July 26­29, 2000. P. 233­246. [383] Waltz D. Generating semantic descriptions from drawings of scenes with shadows. Technical Rep ort AI271. MIT, 1972. [384] Waltz D. L. Understanding line drawings of scenes with shadows // Psychology of Computer Vision. New York: McGraw-Hill, 1975. P. 19­92. [385] Yakhno T. M., Zilb erfaine V. Z., Petrov E. S. Applications of ECLiPSe: Interval domain library // Pro c. PACT97. 1997. [386] Yoko o M. Asynchronous weak-committment search for solving distributed constraint satisfaction problems // Pro c. Principles and Practice of Constraint Programming (CP95). Springer-Verlag, LNCS 976, 1995.


170

. .

[387] Zabih R., McAllester D. A Rearrangement Strategy for Determining Prop ositional Satisfiability // Pro ceedings of The 7th National Conference on Artificial Intelligence. St Paul, 1988. P. 155­160.