Diagnosis of three types of constant faults in read-once contact networks over finite bases

Monther I. Busbait; Mikhail Moshkov

doi:10.1016/j.tcs.2016.03.023

Diagnosis of three types of constant faults in read-once contact networks over finite bases

Monther I. Busbait, Mikhail Moshkov

Research output: Contribution to journal › Article › peer-review

2 Scopus citations

Abstract

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.

Original language	English (US)
Pages (from-to)	26-42
Number of pages	17
Journal	Theoretical Computer Science
Volume	630
DOIs	https://doi.org/10.1016/j.tcs.2016.03.023
State	Published - Mar 24 2016

Bibliographical note

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.

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1016/j.tcs.2016.03.023

https://repository.kaust.edu.sa/bitstream/10754/603716/1/1-s2.0-S0304397516002346-main.pdf

Cite this

@article{228f260a29124087af559ee8637bf90d,

title = "Diagnosis of three types of constant faults in read-once contact networks over finite bases",

abstract = "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.",

author = "Busbait, {Monther I.} and Mikhail Moshkov",

note = "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.",

year = "2016",

month = mar,

day = "24",

doi = "10.1016/j.tcs.2016.03.023",

language = "English (US)",

volume = "630",

pages = "26--42",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

}

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

SN - 0304-3975

VL - 630

SP - 26

EP - 42

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

Diagnosis of three types of constant faults in read-once contact networks over finite bases

Abstract

Bibliographical note

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this