Some decision and counting problems of the Duquenne-Guigues basis of implications

DOI10.1016/j.dam.2007.04.014zbMath1160.68031OpenAlexW2099804491WikidataQ62046333 ScholiaQ62046333MaRDI QIDQ943835

Sergei Obiedkov, Sergei O. Kuznetsov

Publication date: 10 September 2008

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

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

zbMATH Keywords

formal concept analysisfunctional dependencies\#P-completenessDuquenne-Guigues basisimplication basis

Mathematics Subject Classification ID

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

Related Items (15)

A general theory of concept lattice with tractable implication exploration ⋮ Pruning techniques in lincbo for the computation of the duquenne-guigues basis ⋮ Interactive error correction in implicative theories ⋮ On the complexity of enumerating pseudo-intents ⋮ The joy of implications, aka pure Horn formulas: mainly a survey ⋮ Dualization in lattices given by ordered sets of irreducibles ⋮ Succinctness and tractability of closure operator representations ⋮ Parameterized ceteris paribus preferences over atomic conjunctions under conservative semantics ⋮ Optimizations in computing the Duquenne-Guigues basis of implications ⋮ Canonical dichotomous direct bases ⋮ On implication bases in \(n\)-lattices ⋮ Most specific consequences in the description logic \(\mathcal{E} \mathcal{L} \) ⋮ Decision implication canonical basis: a logical perspective ⋮ Computing the Duquenne–Guigues basis: an algorithm for choosing the order ⋮ Quasi-closed elements in fuzzy posets

Cites Work

• Two Basic Algorithms in Concept Analysis
• The Complexity of Enumeration and Reliability Problems
• Comparing performance of algorithms for generating concept lattices
• On computing the size of a lattice and related decision problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Some decision and counting problems of the Duquenne-Guigues basis of implications