Algebraic Reliability. Monomial ideals applied to multi-state system reliability stars

Resumo

In this thesis we study the reliability of multi-state systems using an algebraic approach based on monomial ideals. We consider a system to be a set of components together with a structure function. Both the components and the system are said to be binary if they can reach only two levels of performance: 0 for failure and 1 for working; whereas we call them multi-state if they can take more than two states of performance. The state or level of performance of the system is determined by the state of the components by means of the structure function of the system. The reliability (respectively unreliability) of a system is defined as the probability that the system is in a working (respectively failing) state. For binary systems, it represents the probability that the system is in state 1 (0) while in multi-state systems we have different reliability levels, depending on the number of states of the system. The relation between algebra and reliability theory is provided by monomial ideals: square-free monomial ideals in the binary case and monomial ideals with exponents in the multi-state case. Then, we need to investigate the relationship between squarefree monomial ideals and monomial ideals with exponents. To look into this relationship, we study the operations polarization and depolarization. Polarization is an operation that transforms a monomial ideal into a squarefree one. For each monomial ideal there is a unique polarization. Depolarization is the inverse operation but the resulting monomial ideal with exponents is not unique. In order to find all possible depolarizations of a monomial ideal, we develop a combinatoric tool: support posets. Polarization and depolarization are interesting because the original ideal and its polarization or depolarization share some important properties such as the Betti numbers. However, it is easier to compute them for the square-free monomial ideal. In this thesis we investigate more properties shared between both ideals. Furthermore, we investigate the conditions needed by a poset for being a support poset of a monomial ideal. Once the relation between monomial ideals is treated, we start to work on the analysis multi-state system reliability. There exist different methods to compute the reliability of a system and there are some that are really efficient for specific systems. We thoroughly study multi-state k-out-of-n systems for which we have reviewed the different definitions given in literature. For all of them, we gave an algebraic definition based on monomial ideals. For some variants of k-out-of- n systems we give its algebraic structures associated and explicit formulas for computing its Betti numbers. The algebraic method that we propose is general and provides a good performance, although it is not as fast as the specific ones. We check, in some situations, how the algebraic method proposed behaves in computational terms. To do that, we developed a C++ class with CoCoALib. Not only is this class going to allow us to do some computational experiments, but it is also available for everyone who needs to use it.