Computing premises of a minimal cover of functional dependencies is intractable

DOI10.1016/j.dam.2012.10.026zbMath1263.68046OpenAlexW2074053575MaRDI QIDQ1946215

Mikhail A. Babin, Sergei O. Kuznetsov

Publication date: 18 April 2013

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2012.10.026

zbMATH Keywords

formal concept analysisfunctional dependenciespseudo-intentsminimum basis

Mathematics Subject Classification ID

Database theory (68P15) Knowledge representation (68T30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05)

Related Items (17)

Formal Methods in FCA and Big Data ⋮ A comprehensive survey on formal concept analysis, its research trends and applications ⋮ A general theory of concept lattice with tractable implication exploration ⋮ Mining ℰℒ⊥ Bases with Adaptable Role Depth ⋮ Interactive error correction in implicative theories ⋮ Hierarchical decompositions of implicational bases for the enumeration of meet-irreducible elements ⋮ The joy of implications, aka pure Horn formulas: mainly a survey ⋮ Discovery of the \(D\)-basis in binary tables based on hypergraph dualization ⋮ RQL: a query language for rule discovery in databases ⋮ Algorithms for \(k\)-meet-semidistributive lattices ⋮ Characterizing functional dependencies in formal concept analysis with pattern structures ⋮ Translating between the representations of a ranked convex geometry ⋮ On implication bases in \(n\)-lattices ⋮ A depth-first search algorithm for computing pseudo-closed sets ⋮ Decision implication canonical basis: a logical perspective ⋮ Computing the Duquenne–Guigues basis: an algorithm for choosing the order ⋮ Measuring the Implications of the D-Basis in Analysis of Data in Biomedical Studies

This page was built for publication: Computing premises of a minimal cover of functional dependencies is intractable