|
⇤ ← Revision 1 as of 2003-09-12 01:38:07
Size: 997
Comment:
|
Size: 999
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 11: | Line 11: |
| '''Example:''' x <FONT FACE="Symbol">Î</FONT> {c1, ..., cl} is equivalent to the discution of l constraints x=c1, ..., x=cl. |
'''Example:''' x [<FONT FACE="Symbol">Î</FONT>] {c1, ..., cl} is equivalent to the disjunction of l constraints x=c1, ..., x=cl. |
Needs updating
I do not have a general definition. I suspect that if something is linearly decomposable that it can be written as a set of linear equations.
Unary Constraint Domains
Unary constraint domains are linearly decomposable if there exists a constant d such that, given any set C of BasicConstraints about one variable x, there exists a set C' of basic constraints about x such that |C'| <= d|C|, where |C| is the sum of the sizes of constraints in C for some appropriate notion of size (e.g. number of symbols in a constraint), and the conjunction of any subset of C union C' is a decomposition of C.
What this means is that given a set of basic constraints there is a finite set of constraints that we can union to our original set so that any subset of the conjuction of C and C' can be writen as a disjunction of C' alone.
Example: x [<FONT FACE="Symbol">Î</FONT>] {c1, ..., cl} is equivalent to the disjunction of l constraints x=c1, ..., x=cl.