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: |