AFTD Auto-Formalizing Theoretical Domains

two_counter_machine_update_step

def

The zero-test-free (update-only) one-step relation of a 2-counter machine M: an update transition from c₁.1 to c₂.1 with integer displacement (w₁, w₂) that is realised on the counters.

Statement

def two_counter_machine_update_step {Q : Type*} (M : TwoCounterMachine Q) (c₁ c₂ : Q × ℕ × ℕ) : Prop
Source
step towards symmetric_two_counter_boundary_reachability_semilinear
Verified
20 Oct 2026
Axioms
none listed
Built on 2
  • TwoCounterInstrAn instruction of a 2-counter machine is either an update by a vector of integers (w₁, w₂), or a zero-test on the first counter or the…
  • TwoCounterMachineA structure TwoCounterMachine parameterized by a type of control states Q : Type*, consisting of a single field transitions which is a…

Lean source view module on GitHub

/-- The update (2-VASS) part of the one-step relation: the counters move by (w₁, w₂) and neither counter is inspected. -/
def two_counter_machine_update_step {Q : Type*} (M : TwoCounterMachine Q) (c₁ c₂ : Q × ℕ × ℕ) : Prop :=
  ∃ w₁ w₂ : ℤ,
    (c₁.1, TwoCounterInstr.update w₁ w₂, c₂.1) ∈ M.transitions ∧
    (c₁.2.1 : ℤ) + w₁ = c₂.2.1 ∧ (c₁.2.2 : ℤ) + w₂ = c₂.2.2
See it in the graphDiscuss this resultChallenge it