Documentation

Lean.Meta.Tactic.Grind.Arith.Offset.Main

This module implements a decision procedure for offset constraints of the form:

x + k ≤ y
x ≤ y + k

where k is a numeral. Each constraint is represented as an edge in a weighted graph. The constraint x + k ≤ y is represented as a negative edge. The shortest path between two nodes in the graph corresponds to an implied inequality. When adding a new edge, the state is considered unsatisfiable if the new edge creates a negative cycle. An incremental Floyd-Warshall algorithm is used to find the shortest paths between all nodes. This module can also handle offset equalities of the form x + k = y by representing them with two edges:

x + k ≤ y
y ≤ x + k

The main advantage of this module over a full linear integer arithmetic procedure is its ability to efficiently detect all implied equalities and inequalities.

@[inline]
Equations
    Instances For
      Equations
        Instances For

          Adds an edge u --(k) --> v justified by the proof term p, and then if no negative cycle was created, updates the shortest distance of affected node pairs.

          Equations
            Instances For
              Equations
                Instances For
                  Equations
                    Instances For
                      @[export lean_process_new_offset_eq]
                      Equations
                        Instances For