Implementación computacional del algoritmo LEX para el cálculo de Testores Típicos usando Aprendizaje Simbólico

Abstract

The LEX algorithm for computing typical testors has been notoriously useful in the context of pattern recognition applications. The recently published relationship between typical testors and minimal transversals, potentially increases this algorithm’s usefulness and applicability within the hypergraphs and data mining fields. Unfortunately, the high time-complexity of algorithms in both areas still remains a major obstacle. Therefore, alternatives that can help overcome difficult problems are constantly being researched. In this paper we propose the inclusion of a symbolic learning behavior into the implementation of the LEX algorithm. The incorporated symbolic learning is a general strategy for optimizing the search process, and thus improving the efficiency of typical testors and minimal transversal algorithms. In addition, the performance of the resulting algorithm is assessed using carefully designed benchmark test matrices.