Deciding Disjunctive Linear Arithmetic with SAT
<|reference_start|>Deciding Disjunctive Linear Arithmetic with SAT: Disjunctive Linear Arithmetic (DLA) is a major decidable theory that is supported by almost all existing theorem provers. The theory consists of Boolean combinations of predicates of the form $\Sigma_{j=1}^{n}a_j\cdot x_j \le b$, where the coefficients $a_j$, the bound $b$ and the variables $x_1 >... x_n$ are of type Real ($\mathbb{R}$). We show a reduction to propositional logic from disjunctive linear arithmetic based on Fourier-Motzkin elimination. While the complexity of this procedure is not better than competing techniques, it has practical advantages in solving verification problems. It also promotes the option of deciding a combination of theories by reducing them to this logic. Results from experiments show that this method has a strong advantage over existing techniques when there are many disjunctions in the formula.<|reference_end|>
@article{strichman2004deciding,
    title={Deciding Disjunctive Linear Arithmetic with SAT},
    author={Ofer Strichman},
    journal={arXiv preprint arXiv:cs/0402002},
    year={2004},
    archivePrefix={arXiv},
    eprint={cs/0402002},
    primaryClass={cs.LO}
}