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