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')