TY - JOUR
T1 - Diagnosis of three types of constant faults in read-once contact networks over finite bases
AU - Busbait, Monther I.
AU - Moshkov, Mikhail
N1 - KAUST Repository Item: Exported on 2020-10-01
Acknowledgements: Research reported in this publication was supported by the King Abdullah University of Science and Technology (KAUST).
The authors are greatly indebted to reviewers for useful comments.
PY - 2016/3/24
Y1 - 2016/3/24
N2 - We study the depth of decision trees for diagnosis of three types of constant faults in read-once contact networks over finite bases containing only indecomposable networks. For each basis and each type of faults, we obtain a linear upper bound on the minimum depth of decision trees depending on the number of edges in networks. For bases containing networks with at most 10 edges, we find sharp coefficients for linear bounds.
AB - We study the depth of decision trees for diagnosis of three types of constant faults in read-once contact networks over finite bases containing only indecomposable networks. For each basis and each type of faults, we obtain a linear upper bound on the minimum depth of decision trees depending on the number of edges in networks. For bases containing networks with at most 10 edges, we find sharp coefficients for linear bounds.
UR - http://hdl.handle.net/10754/603716
UR - http://linkinghub.elsevier.com/retrieve/pii/S0304397516002346
UR - http://www.scopus.com/inward/record.url?scp=84979461251&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2016.03.023
DO - 10.1016/j.tcs.2016.03.023
M3 - Article
VL - 630
SP - 26
EP - 42
JO - Theoretical Computer Science
JF - Theoretical Computer Science
SN - 0304-3975
ER -