AFTD Auto-Formalizing Theoretical Domains

NcABP

structure

An affine noncommutative algebraic branching program (ncABP) parameterized by a type F with zero and parameters m, S : ℕ consists of a source and sink in Fin S, edge weights given by AffineForm F m, and the condition that any edge with a nonzero coefficient from u to v satisfies u < v.

Statement

structure NcABP (F : Type*) [Zero F] (m S : ℕ)
Defined in
arXiv:2610.37677, Section 1.1 and Section 3.2
Verified
30 Oct 2026
Axioms
none listed
Built on 1
  • AffineFormAn affine linear form parameterized by a type F and an arity m : ℕ consists of a constant term c0 : F and a tuple of linear coefficients c…
Used by 4
  • ncabp_eval_poly_zero_directionGiven a field F, natural numbers m, S, R, a matrix tuple T : Fin m → Matrix (Fin R) (Fin R) F, and an ncABP A : NcABP F m S such that…
  • ncabp_eval_polyGiven a commutative semiring F, parameters m, S : ℕ, and an ncABP A : NcABP F m S, ncabp_eval_poly A is the polynomial in FreeAlgebra F…
  • is_ncabp_hitting_tupleGiven a field F and natural numbers m, S, R, a tuple of matrices T : Fin m → Matrix (Fin R) (Fin R) F is an ncABP hitting tuple if for…
  • ncabp_matrixGiven a commutative semiring F, parameters m, S : ℕ, and an ncABP A : NcABP F m S, ncabp_matrix A is the transition matrix in Matrix (Fin…

Read back from the Lean

A structure NcABP F m S, parameterized by a type F equipped with a zero element ([Zero F]) and natural numbers m and S, representing an algebraic branching program on S vertices with m variables over F. It consists of: - source : Fin S, a distinguished source vertex; - sink : Fin S, a distinguished sink vertex; - edge : Fin S → Fin S → AffineForm F m, assigning to each pair of vertices u, v : Fin S an affine form in m variables over F; - edge_lt: the property that for all vertices u, v : Fin S, if the affine form edge u v has a non-zero constant term ((edge u v).c0 ≠ 0) or at least one non-zero coefficient (∃ i : Fin m, (edge u v).c i ≠ 0), then u < v in Fin S.

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

/-- An affine noncommutative algebraic branching program (ncABP) with S vertices. -/
structure NcABP (F : Type*) [Zero F] (m S : ℕ) where
  source : Fin S
  sink : Fin S
  edge : Fin S → Fin S → AffineForm F m
  edge_lt : ∀ u v, (edge u v).c0 ≠ 0 ∨ (∃ i, (edge u v).c i ≠ 0) → u < v
See it in the graphDiscuss this resultChallenge it