On the Complexity of Computing Generators of Closed Sets

DOI10.1007/978-3-540-78137-0_12zbMath1131.68537OpenAlexW1577223520MaRDI QIDQ5445331

Miki Hermann, Barış Sertkaya

Publication date: 4 March 2008

Published in: Formal Concept Analysis (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-78137-0_12

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Database theory (68P15) Knowledge representation (68T30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (4)

Introducing the closure structure and the GDPM algorithm for mining and understanding a tabular dataset ⋮ LoCo—A Logic for Configuration Problems ⋮ Unique key Horn functions ⋮ Closure via functional dependence simplification

Cites Work

• The complexity of computing the permanent
• On generating all maximal independent sets
• Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
• Candidate keys for relations
• Subtractive reductions and complete problems for counting complexity classes
• Two Basic Algorithms in Concept Analysis
• The Complexity of Enumeration and Reliability Problems
• Comparing performance of algorithms for generating concept lattices
• Formal Concept Analysis
• Formal Concept Analysis
• 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

This page was built for publication: On the Complexity of Computing Generators of Closed Sets