Amaya

Amaya

An automata-based SMT solver for linear integer arithmetic with quantifiers.

Amaya decides formulae of Presburger arithmetic: linear equations, inequations and congruences over the integers, combined with Boolean connectives and arbitrarily nested quantifiers. It translates a formula into a finite automaton that accepts the binary encodings of the formula’s solutions, so the formula is satisfiable exactly when the automaton accepts a word.

Amaya reads SMT-LIB 2, answers sat or unsat, and can print a model. It is written in Python, with a C++ backend that represents transitions symbolically using the Sylvan decision-diagram library.

x in binary, least significant bit first; the dashed cell is the sign bit.

The minimal automaton that Amaya builds for ∃k. x = 3k + 1, that is, for x mod 3 = 1. Type a number to watch it being read; double circles are final states. See Amaya build it.

How Amaya decides a formula

Amaya follows the classical automata-based approach to Presburger arithmetic, which goes back to Büchi, and strengthens it with algebraic reasoning on the formulae that label the automata’s states.

  1. Encode

    An integer is a word of bits, least significant bit first, ending with the sign bit (two’s complement). The variables of a formula are read in parallel, one track each.

  2. Build

    Every equation, inequation and congruence becomes an automaton whose states are themselves linear constraints, derived from the atom bit by bit. Only the reachable part is built.

  3. Combine

    Conjunction becomes intersection, disjunction union, negation complement, and an existential quantifier the projection of its variable’s track. Determinization and minimization keep the automata small.

  4. Decide

    The formula is satisfiable when its automaton accepts a word. Decoding an accepted word track by track gives a model.

Quantified linear integer arithmetic

Linear constraints over the integers, mod and div by constants, Boolean variables, and any nesting of ∃ and ∀, read from SMT-LIB 2.

Symbolic transitions

The MTBDD backend (--fast) stores transitions as multi-terminal binary decision diagrams, so automata over many variables stay compact. A native backend with explicit symbols is there for experiments.

Preprocessing

Before any automaton is built, Amaya simplifies the formula: GCD rewriting, interval analysis, miniscoping, elimination of variables squeezed between bounds, and more. -O all enables all of them.

Models

For a satisfiable formula, get-sat -p prints values of the free variables that satisfy it.

Every automaton, inspectable

get-sat -o DIR writes every automaton built during the decision procedure in the DOT, VTF or Mata format, together with a graph of the operations that built them.

In the browser

Compiled to WebAssembly with Pyodide and Emscripten, Amaya runs in the playground without installing anything.

Get started

Amaya is written in Python and C++. The Python frontend calls a C++ backend through a Cython wrapper; the backend stores automaton transitions as multi-terminal binary decision diagrams of the Sylvan 1.5 library. The instructions below are for Linux.

Install

# Sylvan 1.5
git clone --depth 1 --branch v1.5.0 https://github.com/trolando/sylvan.git
sed -i 's/-Werror//g' sylvan/CMakeLists.txt
cmake -S sylvan -B sylvan/build -DBUILD_SHARED_LIBS=ON -DCMAKE_POLICY_VERSION_MINIMUM=3.5
cmake --build sylvan/build -j
sudo cmake --install sylvan/build && sudo ldconfig

# Amaya and its C++ backend
git clone --branch devel https://github.com/VeriFIT/amaya.git
cd amaya
python3 -m pip install -r requirements.txt cython setuptools
make -C mtbdd-backend libamaya PYTHON=python3

Run

Save a formula as formula.smt2:

(set-logic LIA)
(declare-fun x () Int)
(declare-fun y () Int)
(assert (and (= (+ x (* 2 y)) 7) (>= x 0) (>= y 0) (> x y)))
(check-sat)

and ask Amaya about it:

# sat
python3 run-amaya.py --fast get-sat formula.smt2
# sat, and the model x = 5, y = 1
python3 run-amaya.py --fast get-sat -p formula.smt2
# with all the preprocessing
python3 run-amaya.py --fast -O all get-sat formula.smt2
# every automaton built, as DOT files in automata/
python3 run-amaya.py --fast get-sat -o automata --output-format dot formula.smt2

run-amaya.py --help lists the global options, run-amaya.py get-sat --help those of the mode. SMT-COMP 2025 ran Amaya with --fast -O all.

No installation

Try it in your browser

The playground runs Amaya compiled to WebAssembly: Python on Pyodide, and the C++ backend and Sylvan compiled with Emscripten. Write a formula in SMT-LIB 2 or pick an example, and look at every automaton Amaya builds on its way to the answer. Everything runs on your computer; nothing is uploaded.

  • Examples from linear systems to the Frobenius coin problem
  • Every intermediate automaton drawn as a graph, with the variable names on its tracks
  • Models, and the automata in the DOT, VTF and Mata formats
  • The same answers as the native build on the 306 benchmarks we compared

Publications

Amaya’s decision procedure, which combines automata with algebraic reasoning, is described in the following paper. If you use Amaya in your research, please cite it.

Peter Habermehl, Vojtěch Havlena, Michal Hečko, Lukáš Holík and Ondřej Lengál

Algebraic Reasoning Meets Automata in Solving Linear Integer Arithmetic

In Computer Aided Verification (CAV 2024), Lecture Notes in Computer Science, pages 42–67. Springer, 2024.

Amaya competed in SMT-COMP 2025, in the LIA and NIA divisions of the single-query track.