Formation of the D-basis from implicational systems using Simplification logic

Abstract

Sets of implications defining closure systems are used as a standard way to represent knowledge, and the search of implicational systems satisfying some criteria constitutes one of the most active topics in the study of closure systems and their applications. Here, we focus on the generation of the D-basis, known to be an ordered direct basis, allowing a very efficient attribute closure computation. We operate with the aggregated D-basis and provide an algorithm to get it from an arbitrary implicational set. The method has been designed on the interrelation between minimal covers and minimal generators, and it is inspired by the inference system of the Simplification Logic. Moreover, we develop an experiment to show the better performance of the new method compared to the earlier version of the algorithm.

Keywords:

• Direct basis
• implicational system
• simplification logic
• minimal cover
• minimal generator

Acknowledgements

We are grateful to three anonymous referees for their careful reading of the paper and numerous suggestions that helped us considerably improve the presentation.

Notes

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work has been partially supported by the Ministry of Economy, Industry and Competitiveness and the European Social Fund [project registration number TIN2014-59471-P].