Algebraic Reasoning Meets Automata in Solving Linear Integer Arithmetic
Open Access
- 26 July 2024
- book chapter
- Published by Springer Nature
- p. 42-67
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 66 references indexed in Scilit:
- 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
- A Theory of Restrictions for Logics and AutomataLecture Notes in Computer Science, 1999
- Mona: Monadic second-order logic in practice1995
- An automata-theoretic approach to Presburger arithmetic constraints1995
- On the value of antiprenexingLecture Notes in Computer Science, 1994
- Liveness of weighted circuits and the diophantine problem of FrobeniusLecture Notes in Computer Science, 1993
- Weak Second‐Order Arithmetic and Finite AutomataMathematical Logic Quarterly, 1960