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 [2009/04/21 19:41] vkuncak |
sav08:qe_for_presburger_arithmetic [2009/04/23 09:44] vkuncak |
||
---|---|---|---|
Line 32: | Line 32: | ||
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$ | 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. | ||
+ | |||
+ | Observation: $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 44: | Line 52: | ||
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 61: | Line 70: | ||
++++ | ++++ | ||
+ | **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 96: | Line 106: | ||
That's it! | That's it! | ||
- | |||
- | |||
- | |||
- | |||
- | |||
===== Example ===== | ===== Example ===== |