Algebraic Reasoning Meets Automata in Solving Linear Integer Arithmetic
Authors:
- Vojtěch HavlenaVHVojtěch Havlena
Preprint
Abstract
We present a new angle on solving quantified linear integer arithmetic based on combining the automata-based approach, where numbers are understood as bitvectors, with ideas from (nowadays prevalent) algebraic approaches, which work directly with numbers. This combination is enabled by a fine-grained version of the duality between automata and arithmetic formulae. In particular, we employ a construction where states of automaton are obtained as derivatives of arithmetic formulae: then every state corresponds to a formula. Optimizations based on techniques and ideas transferred from the world of algebraic methods are used on thousands of automata states, which dramatically amplifies their effect. The merit of this combination of automata with algebraic methods is demonstrated by our prototype implementation being competitive to and even superior to state-of-the-art SMT solvers.Keywords
All Related Versions
This publication has 53 references indexed in Scilit:
- Automata Terms in a Lazy WSkS Decision Procedure2019
- Q3B: An Efficient BDD-based SMT Solver for Quantified Bit-VectorsLecture Notes in Computer Science, 2019
- jMosel: A Stand-Alone Tool and jABC Plugin for M2L(Str)Lecture Notes in Computer Science, 2006
- Representing Arithmetic Constraints with Finite Automata: An Overview2002
- On the Use of Weak Automata for Deciding Linear Arithmetic with Integer and Real Variables2001
- On the Construction of Automata from Linear Arithmetic ConstraintsLecture Notes in Computer Science, 2000
- Diophantine equations, Presburger arithmetic and finite automataLecture Notes in Computer Science, 1996
- An automata-theoretic approach to Presburger arithmetic constraints1995
- On the value of antiprenexingLecture Notes in Computer Science, 1994
- Weak Second‐Order Arithmetic and Finite AutomataMathematical Logic Quarterly, 1960