We study the depth of decision trees for diagnosis of constant faults in read-once contact networks over finite bases. This includes diagnosis of 0-1 faults, 0 faults and 1 faults. For any finite basis, we prove a linear upper bound on the minimum depth of decision tree for diagnosis of constant faults depending on the number of edges in a contact network over that basis. Also, we obtain asymptotic bounds on the depth of decision trees for diagnosis of each type of constant faults depending on the number of edges in contact networks in the worst case per basis. We study the set of indecomposable contact networks with up to 10 edges and obtain sharp coefficients for the linear upper bound for diagnosis of constant faults in contact networks over bases of these indecomposable contact networks. We use a set of algorithms, including one that we create, to obtain the sharp coefficients.
| Identifer | oai:union.ndltd.org:kaust.edu.sa/oai:repository.kaust.edu.sa:10754/316551 |
| Date | 05 1900 |
| Creators | Busbait, Monther I. |
| Contributors | Moshkov, Mikhail, Computer, Electrical and Mathematical Sciences and Engineering (CEMSE) Division, Solovyev, Victor, Vigneron, Antoine E. |
| Source Sets | King Abdullah University of Science and Technology |
| Language | English |
| Detected Language | English |
| Type | Thesis |
| Rights | 2015-05-04, At the time of archiving, the student author of this thesis opted to temporarily restrict access to it. The full text of this thesis became available to the public after the expiration of the embargo on 2015-05-04. |
Page generated in 0.0023 seconds