AFTD Auto-Formalizing Theoretical Domains

nfa_run_count_list

def

The number of runs of the word w in the NFA M from state p to state q: state sequences of length |w|+1 that start at p, end at q and follow the transitions.

Statement

noncomputable def nfa_run_count_list {α σ : Type*} [Fintype σ] (M : NFA α σ) (w : List α) (p q : σ) : ℕ
Source
step towards pell_nfa_run_count_lower_bound
Verified
19 Oct 2026
Axioms
none listed
Used by 7
  • pell_run_encard_eq_countThe set of accepting runs of u_n in A_n has encard equal to the number of runs from q_1 to q_n.
  • pell_prefix_first_letter_vectorAfter appending only the letter c_(i+1) to the prefix, the run counts are P(i+1)-P(i) at q_i, 2P(i) at q_(i+1), (P(i+1)-P(i))+2P(i) at…
  • nfa_run_count_fiberwise_sumThe number of runs of w ++ [a] from p to q is the sum over all states s of the number of runs whose penultimate state is s.
  • pell_prefix_base_countThe prefix c_1c_2 has 1 run from q_1 to q_2, 2 runs from q_1 to q_3, 1 run from q_1 to q_4, and no runs to any other state, in A_n.
  • nfa_run_penultimate_fiberThe number of runs of w ++ [a] from p to q with penultimate state s equals the number of runs of w from p to s if q ∈ M.step s a, and 0…
  • nfa_run_count_list_nilThere is exactly one empty run from p to q if p = q and none otherwise.
  • nfa_run_count_list_concatNumber of runs on w++[a] from p to q equals the sum over s of the number of runs on w from p to s, taken over the predecessors s of q on…

Lean source view module on GitHub

/-- The number of runs of the word w in the NFA M from state p to state q. -/
noncomputable def nfa_run_count_list {α σ : Type*} [Fintype σ] (M : NFA α σ) (w : List α) (p q : σ) : ℕ := {r : Fin (w.length + 1) → σ |
    r 0 = p ∧ r (Fin.last w.length) = q ∧
      ∀ i : Fin w.length, r i.succ ∈ M.step (r i.castSucc) (w.get i)}.ncard
See it in the graphDiscuss this resultChallenge it