AFTD Auto-Formalizing Theoretical Domains

two_counter_machine_zero_test_state_reach

def

q' is reachable from q by a sequence of zero tests while the counter vector is held fixed at p.

Statement

def two_counter_machine_zero_test_state_reach {Q : Type*} (M : TwoCounterMachine Q) (p : ℕ × ℕ) (q q' : Q) : Prop
Source
step towards symmetric_two_counter_boundary_reachability_semilinear
Verified
20 Oct 2026
Axioms
none listed
Built on 2
  • two_counter_machine_zero_test_stepThe zero-test one-step relation of a 2-counter machine M: a zero test on counter i is taken (which requires counter i to be 0) and 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

/-- Zero-test reachability at a frozen counter vector p: the reflexive-transitive closure of the zero-test step relation restricted to the fibre over p. -/
def two_counter_machine_zero_test_state_reach {Q : Type*} (M : TwoCounterMachine Q) (p : ℕ × ℕ) (q q' : Q) : Prop :=
  Relation.ReflTransGen (fun a b : Q => two_counter_machine_zero_test_step M (a, p) (b, p)) q q'
See it in the graphDiscuss this resultChallenge it