TheessenceofconstraintpropagationContentsDefinitionofCSPSol(<D；C>),Sol(C)inshortSol(<D；C>)=whereI={i∈[1…n]|idoesnotappearins}Foreverys-subsequenceCofCandd∈Sol(<D；C>),d[<s>]∈Sol(C).ConstraintpropagationConstraintreductionReducetheconstraintswhilemaintainingequivalenceDomainreductionReducethedomainswhilemaintainingequivalenceConsideranelementd∈D,andasetoffunctionsF={f1,f2,…fk}onD.Arun(off1,f2,…fk)meansainfinitesequenceofnumbersfrom[1,2,..k]Aruni1,i2,…iscalledfairifanyi∈[1,2,..k]appearsinfinitelyoften;PreliminariesWeCallapartialorder(D,⊑)an⊔-poifDcontainstheleastelement,denotedby┴Foreveryincreasingsequenced0⊑d1⊑d2…ofelementsfromD,theupperboundoftheset{d0,d1,d2…},denotedby⊔∞n=0dn,calledthelimitofd0,d1,d2…,exists;Foralla,b∈Dtheleastupperboundoftheset{a,b},denotedbya⊔b,exists;Further,wesaythatAnincreasingsequenced0⊑d1⊑d2…eventuallystabilizesatd,ifforsomej≥0,di=dfori≥j;Apartialordersatisfiesthefinitechainpropertyifeveryincreasingsequenceofitselementseventuallystabilizes.Considerapartialorder(D,⊑),afunctionfonDiscalledInflationaryifx⊑f(x)forallx,Monotonicifx⊑yimpliesf(x)⊑f(y)forallx,yIdempotentiff(f(x))=f(x)forallx.Consideran⊔-po(D,⊑)andF={f1,f2,…fk}onD,allinflationaryandmonotonic.ThenThelimitofeverychaoticiterationofFexistswheref↑jmeansfj(⊥),thejthfolditerationoffstartedat⊥.ConsideraCSPP:=<D;C1,C2,…Ck>.Fori∈[1..k],(F(Ci),⊇)bean⊔-pobaseonCi.WecalltheCartesianproduct(CO,⊑)of(F(Ci),⊇),withi∈[1..k],aconstraint⊔-poassociatedwithP,whilethe(COs,⊑s)withi∈s,s:=i1,i2,…ilCOs={X1×X2×…×Xl|Xj∈F(Cij),forj∈[1..l],}Aboutthe(COs,⊑s)The⊑s-leastelement(⊥)ofCOsisC1×…×ClX1×…×Xl⊑sY1×…×YlifX1×…×XlY1×…×Yl(X1×…×Xl)⊔s(Y1×…×Yl)=(X1×…×Xl)∩(Y1×…×Yl)=(X1∩Y1)×…×(Xl∩Yl)ConsiderafunctiongonCOsThegisinflationary,C⊇g(C)Thegismonotonic.DefinitionofconstraintreductionfunctionConsideraCSP<D;C1,C2,…Ck>togetherwithafamiliesofsetsofF(Ci)basedonCi,fori∈[1..k],andaschemesonk.ByaconstraintsreductionfunctionwithschemeswemeangonCOssuchthatforallC∈COsC⊇g(C)Sol(C)=Sol(g(C))Exampl