AFTD Auto-Formalizing Theoretical Domains

two_counter_machine_is_vass

def

A 2-counter machine M is a vector addition system with states (2-VASS) if every transition in M.transitions is an update transition.

Statement

def two_counter_machine_is_vass {Q : Type*} (M : TwoCounterMachine Q) : Prop
Defined in
arXiv:2610.23495, Sec. 2
Verified
19 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…

Read back from the Lean

Given a type Q and a two-counter machine M : TwoCounterMachine Q, the predicate two_counter_machine_is_vass M asserts that every transition t in M.transitions is an update transition: specifically, for every t ∈ M.transitions, there exist states q, q' : Q and integers w₁, w₂ : ℤ such that t = (q, TwoCounterInstr.update w₁ w₂, q').

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- Predicate asserting that a 2-counter machine is a 2-VASS, having only update transitions. -/
def two_counter_machine_is_vass {Q : Type*} (M : TwoCounterMachine Q) : Prop :=
  ∀ t ∈ M.transitions, ∃ q w₁ w₂ q', t = (q, TwoCounterInstr.update w₁ w₂, q')
See it in the graphDiscuss this resultChallenge it