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