Abstract: New results are obtained in logical data analysis and in the development of recognition procedures based on constructing conjunctive rules. Asymptotically optimal methods of constructing normal forms for characteristic functions of classes are developed. The technique of effective search is improved for the conjunctive rules in the case of incomplete data. Theoretical results are confirmed by experimental estimations.

Keywords: logical recognition procedures, enumeration problem complexity, dualization problem, algorithm with a polynomial delay, asymptotically optimal algorithm, normal form of a logical function, maximal conjunction, transformation of normal forms.

ACM Classification Keywords: F.2.1 Theory of Computation – Analysis of Algorithms and Problem Complexity – Numerical Algorithms and Problems – Computations on matrices, G.2.1. Mathematics of Computing – Discrete Mathematics – Combinatorics – Counting problems.

Link:

ON THE COMPLEXITY OF SEARCH FOR CONJUNCTIVE RULES IN RECOGNITION PROBLEMS

Elena Djukova, Vladimir Nefedov

http://foibg.com/ibs_isc/ibs-16/ibs-16-p07.pdf