This book compares four parameters of problems in arbitrary information systems: complexity of problem representation and complexity of deterministic, nondeterministic, and strongly nondeterministic decision trees for problem solving. Deterministic decision trees are widely used as classifiers, as a means of knowledge representation, and as algorithms. Nondeterministic (strongly nondeterministic) decision trees can be interpreted as systems of true decision rules that cover all objects (ob...

This book explores, within the framework of rough set theory, the complexity of decision trees and decision rule systems and the relationships between them for problems over information systems, for decision tables from closed classes, and for problems involving formal languages. Decision trees and systems of decision rules are widely used as means of representing knowledge, as classifiers that predict decisions for new objects, as well as algorithms for solving various problems of fault d...

In this book, we study decision trees for fault diagnosis in circuits and switching networks, which are among the most fundamental models for computing Boolean functions. We consider two main cases: when the scheme (circuit or switching network) has the same mode of operation for both calculation and diagnostics, and when the scheme has two modes of operation—normal for calculation and special for diagnostics. In the former case, we get mostly negative results, including superpolynomial lo...

This book introduces a fairly universal approach to the design and analysis of exact optimization algorithms for multi-objective combinatorial optimization problems. It proposes the circuits without repetitions representing the sets of feasible solutions along with the increasing and strictly increasing cost functions as a model for such problems. The book designs the algorithms for multi-stage and bi-criteria optimization and for counting the solutions in the framework of this model....

This book is devoted to the transforming of decision rule systems into deterministic and nondeterministic decision trees that recognize the properties of these systems. It continues the development of the so-called syntactic approach to the study of the transformation problem, which assumes that the input data is unknown, and there is only a system of decision rules that must be transformed into decision trees.The book studies the depth and weighted depth of decision trees based on...

In this book, the concept of a hypothesis about the values of all attributes is added to the standard decision tree model, considered, in particular, in test theory and rough set theory. This extension allows us to use the analog of equivalence queries from exact learning and explore decision trees that are based on various combinations of attributes, hypotheses, and proper hypotheses (analog of proper equivalence queries). The two main goals of this book are (i) to provide tools for the e...