AFTD Auto-Formalizing Theoretical Domains

path_cut_word

def

path_cut_word n S is the length-(n-1) boolean word whose j-th letter records whether the j-th edge of the path pathGraph n (i.e. the edge between vertex j and vertex j+1) crosses the cut (S, Sᶜ). So letter j is true exactly when exactly one of j, j+1 lies in S.

Statement

def path_cut_word (n : ℕ) (S : Finset (Fin n)) : List Bool
Source
step towards claw_free_tree_graph_state_mmi
Verified
01 Nov 2026
Axioms
none listed
Used by 3
  • path_cut_word_odd_run_ineqFor a four-partition A,B,C,D of the vertices of the path P_n, the sum of the numbers of maximal odd-length crossing runs for A, B, C and D…
  • path_cut_word_count_cancelFor a four-partition A,B,C,D of the vertices of the path P_n, the total number of edges crossing the cuts defined by A, B, C, D equals the…
  • path_cert_word_eq_cut_wordThe Boolean edge word used by the finite-state certificate is the ordinary path cut word of the corresponding color mask.

Lean source view module on GitHub

/-- Indicator word of the crossing edges of `S` along the path `pathGraph n`. -/
def path_cut_word (n : ℕ) (S : Finset (Fin n)) : List Bool := List.ofFn (fun j : Fin (n - 1) =>
    (decide ((⟨j.val, by omega⟩ : Fin n) ∈ S)) != (decide ((⟨j.val + 1, by omega⟩ : Fin n) ∈ S)))
See it in the graphDiscuss this resultChallenge it