Keywords: complex stochastic Boolean systems, reliability engineering, intrinsic order, top binary n-tuples, bottom binary n-tuples, generalized top binary n-tuples, generalized bottom binary n-tuples.

A complex stochastic Boolean system (CSBS) is a system depending on an arbitrary number n of random Boolean variables x₁,...,x_n. Each one of the 2ⁿ possible situations associated to such a system is given by a binary n-tuple u in {0,1}ⁿ of 0s and 1s, and it has its own occurrence probability Pr{u}.

The intrinsic order criterion [1,2] leads us to establish a partition of the set {0,1}ⁿ of binary n-tuples into three kinds of binary strings: top, bottom and jumping binary n-tuples. A binary n-tuple u is called top (bottom, respectively) if its occurrence probability Pr{u} is always among the 2ⁿ largest (smallest, respectively) ones. A binary n-tuple u is called jumping if it is neither top nor bottom. Top and bottom n-tuples has been characterized in [3].

In this paper, we generalize these three kinds of binary strings by defining the k-top, k-bottom and k-jumping binary n-tuples (1 <= k <= 2ⁿ). A binary n-tuple u is called k-top (k-bottom, respectively) if its occurrence probability Pr{u} is always among the k largest (smallest, respectively) ones. A binary n-tuple u is called k-jumping if it is neither k-top nor k-bottom. We present a symmetry property that reduces the study of the k-bottom strings to the study of the k-top strings simply by changing 0s to 1s and 1s to 0s in the binary n-tuples (i.e, interchanging the role of 0s and 1s). We establish some properties and necessary conditions for both the k-top and k-bottom binary n-tuples.

Next, we present a necessary and sufficient condition for the k-top binary n-tuples. To state this characterization theorem, we first determine the cardinality of the set C^u of all binary binary n-tuples that are intrinsically less than or equal to a given n-tuple u. The set C^u has been widely studied in [4]. For characterizing the k-bottom binary n-tuples it is enough to use the above mentioned symmetry property. For identifying the k-jumping binary n-tuples it is enough to use the fact that they are neither k-top nor k-bottom. These theoretical results may be applied to the reliability analysis of technical systems (or, in general, CSBSs arising from many scientific or engineering areas) described by a stochastic Boolean function.

1

L. González, "N-tuples of 0s and 1s: Necessary and Sufficient Conditions for Intrinsic Order", Lecture Notes in Computer Science, 2667(1), 937-946, 2003. doi:10.1007/3-540-44839-X_99

2

L. González, D. García, B. Galván, "An Intrinsic Order Criterion to Evaluate Large, Complex Fault Trees", IEEE Transactions on Reliability, 53(3), 297-305, 2004. doi:10.1109/TR.2004.833307

3

L. González, "A New Method for Ordering Binary States Probabilities in Reliability and Risk Analysis", Lecture Notes in Computer Science, 2329(1), 137-146, 2002. doi:10.1007/3-540-46043-8_13

4

L. González, "Algorithm comparing binary string probabilities in complex stochastic Boolean systems using intrinsic order graph", Advances in Complex Systems, 10, 111-143, 2007. doi:10.1142/S0219525907001136

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £95 +P&P)