Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
sav08:qe_for_presburger_arithmetic [2009/04/23 09:44] vkuncak |
sav08:qe_for_presburger_arithmetic [2012/03/09 10:44] vkuncak |
||
|---|---|---|---|
| Line 5: | Line 5: | ||
| 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]]). | ||
| + | Running example: | ||
| + | \[ | ||
| + | \exists y. 3 y - 2 x + 1 > - x \land 2y - 6 < z \land 4 \mid 5y + 1 | ||
| + | \] | ||
| ===== Normalizing Conjunctions of Literals ===== | ===== Normalizing Conjunctions of Literals ===== | ||
| Line 32: | Line 35: | ||
| 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 ===== | ||
| Line 41: | Line 43: | ||
| To eliminate $\exists y$ from such conjunction, we wish to ensure that the coefficient next to $y$ is one or minus one. | 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. | + | 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|$. | 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|$. | ||
| Line 96: | Line 98: | ||
| We first drop all constraints except divisibility, obtaining $F_2(x)$ | We first drop all constraints except divisibility, obtaining $F_2(x)$ | ||
| \[ | \[ | ||
| - | \bigwedge_{i=1}^D K_i \mid (x_i + t_i) | + | \bigwedge_{i=1}^D K_i \mid (x + t_i) |
| \] | \] | ||
| and then eliminate quantifier as | and then eliminate quantifier as | ||
| Line 130: | Line 132: | ||
| $\exists res, i. \neg true$\\ | $\exists res, i. \neg true$\\ | ||
| $false$ | $false$ | ||
| + | |||
| + | |||
| ===== Some Improvements ===== | ===== Some Improvements ===== | ||
| Avoid transforming to conjunctions of literals: work directly on negation-normal form. | Avoid transforming to conjunctions of literals: work directly on negation-normal form. | ||
| + | * the technique is similar to what we described for conjunctive normal form | ||
| - | See Section 7.2 of the [[Calculus of Computation Textbook]]. | + | This is the Cooper's algorithm |
| + | * {{sav09:reddyloveland78presburgerboundedalternation.pdf|Reddy, Loveland: Presburger Arithmetic with Bounded Quantifier Alternation}} (gives a slight improvement of the original Cooper's algorithm) | ||
| + | * Section 7.2 of the [[Calculus of Computation Textbook]] | ||
| ===== References ===== | ===== References ===== | ||