On the intractability of computing the Duquenne-Guigues base

MaRDI QIDQ5429564zbMATH OpenFDO

Authors Sergei O. Kuznetsov

Publication date 30 November 2007

Full work available at URL http://www.jucs.org/jucs_10_8/on_the_intractability_of

zbMATH Keywords

computational complexityimplication base

Mathematics Subject Classification ID

Galois correspondences, closure operators (in relation to ordered sets) (06A15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Knowledge representation (68T30)

Recommendations

• Some decision and counting problems of the Duquenne-Guigues basis of implications
• Formal Concept Analysis
• Some Computational Problems Related to Pseudo-intents
• Formal Concept Analysis
• Formal Concept Analysis

Cited in

(29)

• Probabilistic generalization of formal concepts
• A depth-first search algorithm for computing pseudo-closed sets
• Steps towards causal Formal Concept Analysis
• Pruning techniques in LinCbO for computation of the Duquenne-Guigues basis
• Approximate computation of exact association rules
• Knowledge cores in large formal contexts
• A general theory of concept lattice with tractable implication exploration
• Fast algorithms for implication bases and attribute exploration using proper premises
• On implication bases in \(n\)-lattices
• Attribute-incremental construction of the canonical implication basis
• Closure-based constraints in formal concept analysis
• From equivalence queries to PAC learning: the case of implication theories
• Machine learning with probabilistic law discovery: a concise introduction
• Some complexity results about essential closed sets
• Formal Methods in FCA and Big Data
• Succinctness and tractability of closure operator representations
• THE BASE PROBLEM FOR D0L PARIKH SETS
• On the Complexity of Computing Generators of Closed Sets
• Formal Concept Analysis
• Formal Concept Analysis
• LinCbO: fast algorithm for computation of the Duquenne-Guigues basis
• Pruning techniques in lincbo for the computation of the duquenne-guigues basis
• Mining ℰℒ⊥ Bases with Adaptable Role Depth
• Hierarchical decompositions of implicational bases for the enumeration of meet-irreducible elements
• On the complexity of enumerating pseudo-intents
• Formal concept analysis: from knowledge discovery to knowledge processing
• Decision implication canonical basis: a logical perspective
• Interactive error correction in implicative theories
• Some decision and counting problems of the Duquenne-Guigues basis of implications

This page was built for publication: On the intractability of computing the Duquenne-Guigues base

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