Theorem 5.1 — counting control sequences that reach a state while avoiding forbidden states
ProvedDelayedBCN.Controllability.numToStateAvoiding_eq_sumConsider a delayed Boolean control network with delay length and transition-count matrix . Let be a set of forbidden states, the set of trajectories containing at least one state of , and the matrix obtained from by substituting zeros in the rows and columns of the trajectories in . Let be an initial trajectory, a destination state and the trajectories whose current state is . For every integer , the number of control sequences of length that steer the network from to while avoiding satisfies
The result reduces state avoidance to trajectory avoidance, so that the forbidden-state problem is solved by the matrix algorithm of Proposition 3.5.
Formalization Note "Avoiding " is read as the theorem's middle term: no state , (the initial states included), belongs to , equivalently no trajectory lies in . Both equalities are stated; as in the paper.
import Mathlib import Definitions.Def_DelayedBCN_Controllability_Model import Definitions.Def_DelayedBCN_Controllability_Matrix
namespace DelayedBCN.Controllability
/-- Theorem 5.1 (Lu et al. 2016, pp. 489–490): for `k > 0`,
`ℕ₂(k; a, bs, Cs) = ∑_{b ∈ Ξ^{bs}_μ} ℕ₁(k; a, b, Ξ^{Cs}) = ∑_{b ∈ Ξ^{bs}_μ} bᵀ (Q_{Ξ^{Cs}})^k a`. -/
theorem numToStateAvoiding_eq_sum {μ n m : ℕ} [NeZero μ] (F : Network μ n m)
(Cs : Finset (State n)) (a : Traj μ n) (bs : State n) (k : ℕ) (hk : 0 < k) :
numToStateAvoiding F k a bs Cs = ∑ b ∈ xiLast bs, numAvoiding F k a b (xiForbidden Cs) ∧
numToStateAvoiding F k a bs Cs =
∑ b ∈ xiLast bs, (QZeroed F (xiForbidden Cs) ^ k) b a := by sorry
end DelayedBCN.Controllability
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Setup.
- ; are arbitrary natural numbers.
- is an arbitrary network. One step is .
- is any finite set of states.
- is a trajectory and is a state.
- is a natural number with .
Claim. Both of the following equalities hold:
The symbols mean the following:
- . For , and .
- . The number of that satisfy both of these:
- the last entry of is ;
- no entry, at any position, of any of lies in .
- . The set of trajectories whose last entry is .
- . The set of trajectories having at least one entry in .
- . The number of with and for all .
- and . , and is with every row and column indexed by a trajectory in set to zero. The power is taken over the natural numbers.
Degenerate cases.
- . Excluded by hypothesis.
- Empty . is empty, and the statement reduces to the unrestricted counts with .
- or forbidden. If contains a state of , or , all three expressions are asserted equal, and the left side is then .
- contains every state. Every trajectory is forbidden and all quantities are .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.