Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision | Next revision Both sides next revision | ||
|
complexity [2007/10/04 23:18] philippe.suter |
complexity [2007/10/05 01:00] philippe.suter |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| ===== Complexity of the verification process ===== | ===== Complexity of the verification process ===== | ||
| + | |||
| ==== Preliminary remarks ==== | ==== Preliminary remarks ==== | ||
| Line 14: | Line 15: | ||
| === Consistency of the dimensions of the cartesian products === | === Consistency of the dimensions of the cartesian products === | ||
| - | We know that to every pattern corresponds one cartesian product. By construction, the dimension of these products is always the same since it corresponds to $max_p(E)$. In particular, this means that taking the union of two "pattern sets" will yield yet another cartesian product with the same cardinality. | + | For every pattern, we build a cartesian product representing the set of inputs which it would match. By construction, the dimension of these products is always the same since it corresponds to $max_p(E)$. In particular, this means that taking the union of two "pattern sets" will yield yet another cartesian product with the same cardinality. |
| Note that we now also have: | Note that we now also have: | ||