Abstract: State/event fault trees provide an expressive formalism for modeling software-controlled and dynamic safety-critical systems, but their analysis may suffer from state-space explosion. Building on the top-down reachability perspective proposed for state/event fault trees and on the combinatorial insight of conservative Petri-net state-space estimation, this paper addresses the related problem of estimating the state-space size before constructing the reachability graph. The proposed method formulates the estimation as a combinatorial counting problem: the initial universe of possible configurations is represented as the Cartesian product of component-state sets, whereas known unreachable state combinations are treated as exceptions. The Subtraction Principle is used to remove configurations containing these exceptions, and the Inclusion-Exclusion Principle is applied to avoid over-subtraction when exceptions overlap. The method can be viewed as a state/event-fault-tree-specific refinement of conservative-Petri-net state-space size estimation: it preserves the structural counting advantage while incorporating mutual-exclusion constraints between component states. If the supplied exclusion constraints are sound and complete, the computation gives the exact count; if they are sound but incomplete, it gives an upper-bound estimate. The formulation provides a compact and a-priori way to reason about the expected size of a state/event fault tree state space before full reachability generation is attempted.

Key words: state/event fault trees, state-space size estimation, reachability analysis, combinatorics, inclusion-exclusion, fault tree analysis