LinCbO: fast algorithm for computation of the Duquenne-Guigues basis

DOI10.1016/J.INS.2021.04.104MaRDI QIDQ6071284zbMATH OpenOpenAlexFDO

Authors Radek Janostik, Jan Konecny, Petr Krajca

Publication date 23 November 2023

Published in Information Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2011.04928

zbMATH Keywords

attribute implicationsclosuresminimalizationnon-redundancy

Mathematics Subject Classification ID

Knowledge representation (68T30)

Abstract: We propose and evaluate a novel algorithm for computation of the Duquenne-Guigues basis which combines Close-by-One and LinClosure algorithms. This combination enables us to reuse attribute counters used in LinClosure and speed up the computation. Our experimental evaluation shows that it is the most efficient algorithm for computation of the Duquenne-Guigues basis.

Recommendations

• Pruning techniques in lincbo for the computation of the duquenne-guigues basis
• Optimizations in computing the Duquenne-Guigues basis of implications
• Computing the Duquenne-Guigues basis: an algorithm for choosing the order
• A depth-first search algorithm for computing pseudo-closed sets
• Some decision and counting problems of the Duquenne-Guigues basis of implications

Cites work

• A `best-of-breed' approach for designing a fast algorithm for computing fixpoints of Galois connections
• Attribute dependencies for data with grades I^,
• Attribute-incremental construction of the canonical implication basis
• Closure via functional dependence simplification
• Closure-based constraints in formal concept analysis
• Comparing performance of algorithms for generating concept lattices
• Exploiting the potential of concept lattices for information retrieval with credo
• Fast algorithm for computing fixpoints of Galois connections induced by object-attribute relational data
• Finding all closed sets: A general approach
• Graded LinClosure and Its Role in Relational Data Analysis
• scientific article; zbMATH DE number 3823168 (Why is no real title available?)
• scientific article; zbMATH DE number 1249514 (Why is no real title available?)
• scientific article; zbMATH DE number 7635224 (Why is no real title available?)
• Making use of empty intersections to improve the performance of CbO-type algorithms
• Minimal bases of temporal attribute implications
• On the intractability of computing the Duquenne-Guigues base
• Optimizations in computing the Duquenne-Guigues basis of implications

Cited in

(1)

• Pruning techniques in lincbo for the computation of the duquenne-guigues basis

This page was built for publication: LinCbO: fast algorithm for computation of the Duquenne-Guigues basis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6071284)