Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
|
sav08:qe_for_presburger_arithmetic [2008/04/17 10:42] david |
sav08:qe_for_presburger_arithmetic [2009/04/23 09:27] vkuncak |
||
|---|---|---|---|
| Line 4: | Line 4: | ||
| We consider elimination of a quantifier from a conjunction of literals (because [[QE from Conjunction of Literals Suffices]]). | We consider elimination of a quantifier from a conjunction of literals (because [[QE from Conjunction of Literals Suffices]]). | ||
| + | |||
| + | |||
| ===== Normalizing Conjunctions of Literals ===== | ===== Normalizing Conjunctions of Literals ===== | ||
| Line 29: | Line 31: | ||
| $t_1 < t_2$ becomes ++| $0 < t_2 - t_1$++ | $t_1 < t_2$ becomes ++| $0 < t_2 - t_1$++ | ||
| - | We obtain a disjunction of conjunctions of literals of the form $0 < t$ and $K \mid t$ where $t$ are | + | We obtain a disjunction of conjunctions of literals of the form $0 < t$ and $K \mid t$ where $t$ are of the form $K_0 + \sum_{i=1}^n K_i \cdot x_i$ |
| ===== Exposing the Variable to Eliminate ===== | ===== Exposing the Variable to Eliminate ===== | ||
| - | By previous transformations, we are eliminating $y$ from conjunction $F(y)$ of $0 < t$ and $K \mid t$ where $t$ is a linear term. To eliminate $\exists y$ from such conjunction, we wish to ensure that the coefficient next to $y$ is one or minus one. Note that $0 < t$ is equivalent to $0 < c\, t$ and $K \mid t$ is equivalent to $c\, K \mid c\, t$ for $c$ a positive integer. If $K_1,\ldots,K_n$ are all coefficients next to $y$ in the formula, let $M$ be a positive integer such that $K_i \mid M$ for all $i$, $1 \le i \le n$ (for example, let $M$ be the least common multiple of $K_1,\ldots,K_n$). Multiply each literal where $y$ occurs in subterm $K_i y$ by constant $M/|K_i|$. | + | By previous transformations, we are eliminating $y$ from conjunction $F(y)$ of $0 < t$ and $K \mid t$ where $t$ is a linear term. |
| + | |||
| + | **Coefficient next to** $y$: | ||
| + | To eliminate $\exists y$ from such conjunction, we wish to ensure that the coefficient next to $y$ is one or minus one. Note that $0 < t$ is equivalent to $0 < c\, t$ and $K \mid t$ is equivalent to $c\, K \mid c\, t$ for $c$ a positive integer. If $K_1,\ldots,K_n$ are all coefficients next to $y$ in the formula, let $M$ be a positive integer such that $K_i \mid M$ for all $i$, $1 \le i \le n$ (for example, let $M$ be the least common multiple of $K_1,\ldots,K_n$). Multiply each literal where $y$ occurs in subterm $K_i y$ by constant $M/|K_i|$. | ||
| What is the coefficient next to $y$ in the resulting formula? ++| either $M$ or $-M$ ++ | What is the coefficient next to $y$ in the resulting formula? ++| either $M$ or $-M$ ++ | ||
| Line 42: | Line 47: | ||
| What is the coefficient next to $y$ in the resulting formula? ++| either $1$ or $-1$ ++ | What is the coefficient next to $y$ in the resulting formula? ++| either $1$ or $-1$ ++ | ||
| + | **Lower and upper bounds:** | ||
| Consider the coefficient next to $x$ in $0 < t$. If it is $-1$, move the term to left side. If it is $1$, move the remaining terms to the left side. We obtain formula $F_1(x)$ of the form | Consider the coefficient next to $x$ in $0 < t$. If it is $-1$, move the term to left side. If it is $1$, move the remaining terms to the left side. We obtain formula $F_1(x)$ of the form | ||
| \[ | \[ | ||
| Line 59: | Line 65: | ||
| ++++ | ++++ | ||
| + | **Replacing variable by test terms:** | ||
| There is a an alternative way to express the above condition by replacing $F_1(x)$ with $\bigvee_k F_1(t_k)$ where $t_k$ do not contain $x$. This is a common technique in quantifier elimination. Note that if $F_1(t_k)$ holds then certainly $\exists x. F_1(x)$. | There is a an alternative way to express the above condition by replacing $F_1(x)$ with $\bigvee_k F_1(t_k)$ where $t_k$ do not contain $x$. This is a common technique in quantifier elimination. Note that if $F_1(t_k)$ holds then certainly $\exists x. F_1(x)$. | ||
| Line 100: | Line 107: | ||
| How can we prove such verification condition? | How can we prove such verification condition? | ||
| + | |||
| + | The invariant of this code example is : $F = (res + 2i = 2x \wedge i' = i - 1 \wedge res' = res + 2) \rightarrow res' + 2i' = 2x$ | ||
| + | |||
| + | We have to find out if | ||
| + | $\neg F$ | ||
| + | is satisfiable. | ||
| + | |||
| + | $\exists res, res',i, i'. \neg F$ | ||
| + | |||
| + | We can eliminate quantifiers with equalities: $i'= i-1$ and $res' = res + 2$ | ||
| + | |||
| + | $res' + 2i'$ becomes $res + 2 + 2(i-1)$, and $\exists i', res' $ can be removed | ||
| + | |||
| + | Finally : | ||
| + | |||
| + | $\exists res, i. \neg (res + 2i = 2x \rightarrow res + 2 + 2(i-1) = 2x)$\\ | ||
| + | $\exists res, i. \neg (res + 2i = 2x \rightarrow res + 2i = 2x)$\\ | ||
| + | $\exists res, i. \neg true$\\ | ||
| + | $false$ | ||
| ===== Some Improvements ===== | ===== Some Improvements ===== | ||
| Line 106: | Line 132: | ||
| See Section 7.2 of the [[Calculus of Computation Textbook]]. | See Section 7.2 of the [[Calculus of Computation Textbook]]. | ||
| + | |||
| ===== References ===== | ===== References ===== | ||
| Line 113: | Line 140: | ||
| See Section 7.2 of the [[Calculus of Computation Textbook]] for a description of more efficient Cooper's algorithm. | See Section 7.2 of the [[Calculus of Computation Textbook]] for a description of more efficient Cooper's algorithm. | ||
| - | [[http://doi.acm.org/10.1145/135226.135233|A practical algorithm for exact array dependence analysis]] (suitable for a project) | + | [[http://doi.acm.org/10.1145/135226.135233|A practical algorithm for exact array dependence analysis]] |