Comparative Analysis of Deterministic and Nondeterministic Decision Trees (Intelligent Systems Reference Library, 179)

Preface
Acknowledgements
Contents
1 Introduction
	1.1 Main Directions of Study
		1.1.1 Decision Tables with Many-Valued Decisions
		1.1.2 Local Approach to Study of Decision Trees
		1.1.3 Global Approach to Study of Decision Trees
	1.2 Contents of Book
		1.2.1 Part I. Decision Trees for Decision Tables
		1.2.2 Part II. Decision Trees for Problems. Local Approach
		1.2.3 Part III. Decision Trees for Problems. Global Approach
		1.2.4 Index and Notation
	1.3 Use of Book
	References
Part I Decision Trees for Decision Tables
2 Basic Definitions and Notation
	2.1 Common Notions
	2.2 Decision Tables
	2.3 Schemes of Decision Trees
	2.4 Different Types of Decision Trees for Decision Tables
	2.5 Complexity Functions
	2.6 Enumerated Signatures
	References
3 Lower Bounds on Complexity  of Deterministic Decision Trees  for Decision Tables
	3.1 Definitions and Notation
	3.2 Auxiliary Statements
	3.3 Lower Bounds
	3.4 Approach to Proof of Lower Bounds
	References
4 Upper Bounds on Complexity and Algorithms for Construction of Deterministic Decision Trees for Decision Tables. First Approach
	4.1 Difference-Bounded Uncertainty Measures for Decision Tables
	4.2 Process Uρ of Schema Construction
	4.3 Auxiliary Statements
	4.4 Upper Bounds on ψ(Uρ(T,γ,ψ))
	4.5 Corollaries
	4.6 Algorithm Uρ,,ψ
	4.7 Algorithms Uρ,GHρ,h, Uρ,RHρm+1,h, and Uρ,Hρm+1,h
	4.8 Algorithms Wρ,GHρ,h, Wρ,RHρ2,h, and Wρ,Hρ2,h
	References
5 Upper Bounds and Algorithms  for Construction of Deterministic  Decision Trees for Decision Tables. Second Approach
	5.1 Reduced Deterministic Decision Trees for Decision Tables
	5.2 Additive-Bounded Uncertainty Measures for Decision Tables
	5.3 Process Yρ,mathcalN of Schema Construction
	5.4 Upper Bounds on ψρd(T)
	5.5 Upper Bounds on hρd(T)
	5.6 Algorithm Yρ,η,,ψ
	References
6 Bounds on Complexity and Algorithms for Construction of Nondeterministic and Strongly Nondeterministic Decision Trees for Decision Tables
	6.1 Bounds on ψρa(T) and ψρs(T)
	6.2 Approach to Proof of Lower Bounds on ψρs(T) and ψρa(T)
	6.3 Algorithms Vρ,,ψa  and Vρ,,ψs
	Reference
7 Closed Classes of Boolean Functions
	7.1 Main Definitions and Notation
	7.2 Auxiliary Statements
	7.3 Bounds for Individual Closed Classes
	7.4 Bounds for Arbitrary Closed Classes
	References
8 Algorithmic Problems
	8.1 Relationships Among Algorithmic Problems
	8.2 Examples of Decidable and Undecidable Problems
	8.3 Possible Variants of Algorithmic Problem Behavior
	8.4 Examples of Problems with Polynomial Complexity
	8.5 Examples of NP-Hard Problems
	References
Part II Decision Trees for Problems. Local Approach
9 Basic Definitions and Notation
	9.1 Information Systems
	9.2 Decision Trees
	9.3 Problem Schemes and Problems
	9.4 Decision Trees Solving Problems
	9.5 Decision Tree Schemes Corresponding to Problem Schemes
	9.6 Complexity Functions
	9.7 Matrices of Upper and Lower Local Bounds for Sccf-Triple
	9.8 Types of Functions and Sccf-Triples
	References
10 Main Reductions
	10.1 Decision Trees and Decision Tree Schemes
	10.2 Arbitrary Classes of Information Systems and One-Element Classes of Information Systems
	10.3 Upper and Lower Bounds
	References
11 Functions on Main Diagonal and Below
	11.1 Function  τii
	11.2 Function  τdi
	11.3 Function  τdd
	11.4 Functions  τai,  τad,  τaa,  τsi,  τsd,  τsa, and  τss
	References
12 Functions Over Main Diagonal
	12.1 Functions τid, τia, and τis
	12.2 Function  τas
	12.3 Function  τds
	12.4 Function  τda
	References
13 Local Upper Types of Restricted Sccf-Triples
	13.1 Possible Local Upper Types
	13.2 Examples of Restricted Sccf-Triples
	13.3 Main Statements
	Reference
14 Bounds Inside Types
	14.1 Set ρ(1)
	14.2 Set ρ(2)
	14.3 Set ρ(3)
	14.4 Set ρ(4)
	14.5 Set ρ(5)
	14.6 Set ρ(6)
	Reference
15 Matrices of Lower Local Bounds
	15.1 Possible Local Lower Types
	15.2 Auxiliary Statements
	15.3 Bounds Inside Types
	Reference
16 Algorithmic Problems. Local Approach
	16.1 Relationships Among Algorithmic Problems
	16.2 Algorithm for Table Tρ(z,K) Construction
	16.3 Algorithms for Construction of Decision Tree Schemes
	References
Part III Decision Trees for Problems. Global Approach
17 Basic Definitions and Notation
	17.1 Complexity Functions
	17.2 Matrices of Upper and Lower Global Bounds  for Sccf-Triple
	17.3 Types of Sccf-Triples
	References
18 Some Reductions
	18.1 Problem Schemes and Decision Tables
	18.2 Arbitrary Classes of Information Systems  and One-Element Classes of Information Systems
	18.3 Set mathbbtildeR
	18.4 Primitive Composition of Disjoint Simple Sccf-Triples
	18.5 Composition of Simple Sccf-Triples
	18.6 Operation rotimes
	18.7 Relationships Between Ψτ and  τ
	18.8 Transition from One Signature to Another
	References
19 Functions on Main Diagonal and Below
	19.1 Preliminary Lemmas
	19.2 Function Ψτii
	19.3 Function Ψτdi
	19.4 Function Ψτdd
	19.5 Functions Ψτai, Ψτad, Ψτaa, Ψτsi, Ψτsd, Ψτsa, and Ψτss
	References
20 Functions over Main Diagonal
	20.1 Functions Ψτid, Ψτia, and Ψτis
	20.2 Function Ψτas
	20.3 Function Ψτds
	20.4 Function Ψτda
	Reference
21 Possible Global Upper Types  of Sccf-Triples
	21.1 Possible Global Upper Types
	21.2 Criteria for Equalities Typ Ψτ=Tpj
	21.3 Global Upper Type of Composition of Simple Sccf-Triples
	References
22 Realizable Global Upper Types  of Sccf-Triples
	22.1 Sccf-Triples from Ws(1)
	22.2 Sccf-Triples from Ws(7)
	22.3 Sccf-Triples from Ws(2) and Ws(9)
	22.4 Sccf-Triples from Ws(8)
	22.5 Sccf-Triples from Ws(4)
	22.6 Sccf-Triples from Ws(6)
	22.7 Sccf-Triples from Ws(3)
	22.8 Sccf-Triples from Ws(5)
	22.9 Sccf-Triples from Ws(10)
	22.10 Sccf-Triples τ with TypΨτ=Tp11
	22.11 Main Statements
	Reference
23 Bounds Inside Types
	23.1 Auxiliary Statements
	23.2 Set Wρ(1)
	23.3 Set Wρ(2)
	23.4 Set Wρ(3)
	23.5 Set Wρ(4)
	23.6 Set Wρ(5)
	23.7 Set Wρ(6)
	23.8 Set Wρ(7)
	23.9 Set Wρ(8)
	23.10 Set Wρ(9)
	23.11 Set Wρ(10)
	Reference
24 Matrices of Lower Global Bounds
	24.1 Possible Global Lower Types
	24.2 Auxiliary Statements
	24.3 Bounds Inside Types
	Reference
25 Algorithmic Problems. Global Approach
	25.1 Some Relationships Among Algorithmic Problems
	25.2 Proper Weighted Depth
	References
Appendix  Final Remarks
Appendix  Notation
Symbol Index
Appendix  Index
Index