A Minimal-Automaton-Based Algorithm for the Reliability of Con(d,k, n) Systems期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

按检索

A Minimal-Automaton-Based Algorithm for the Reliability of Con(d,k, n) Systems

Authors:	Chang Jen-Chun Chen Rong-Jaye Hwang Frank K

Institution:	(1) Department of Information Management, Ming Hsin Institute of Technology, Hsin-Chu, Taiwan;(2) Department of Computer Science and Information Engineering, National Chiao Tung University, Hsin-Chu, Taiwan;(3) Department of Applied Mathematics, National Chiao Tung University, Hsin-Chu, Taiwan

Abstract:	A d-within-consecutive-k-out-of-n system, abbreviated as Con(d, k, n), is a linear system of n components in a line which fails if and only if there exists a set of k consecutive components containing at least d failed ones. So far the fastest algorithm to compute the reliability of Con(d, k, n) is Hwang and Wright's $O\left( {\left\| L \right\|^3 n} \right)$ algorithm published in 1997, where $\left\| L \right\| = O\left( {2^k } \right)$ . In this paper we use automata theory to reduce $\left\| L \right\|$ to $\left( {\begin{array}{{20}c} k \\ {d - 1} \\ \end{array} } \right) + 1$ . For d small or close to k, we have reduced $\left\| L \right\|$ from exponentially many (in k) to polynomially many. The computational complexity of our final algorithm is $O\left( {\left\| L \right\|^2 + \left\| L \right\|n} \right)$ , where $\left\| L \right\| = \left( {\begin{array}{{20}c} k \\ {d - 1} \\ \end{array} } \right) + 1$ .

Keywords:	consecutive system Con(d k n) system reliability algorithm complexity
本文献已被 SpringerLink 等数据库收录！

设为首页 | 免责声明 | 关于勤云 | 加入收藏