On the Complexity of Computing Generators of Closed Sets

DOI10.1007/978-3-540-78137-0_12MaRDI QIDQ5445331zbMATHOpenAlexFDO

Authors 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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Knowledge representation (68T30) Database theory (68P15)

Recommendations

• Some complexity results about essential closed sets
• Formal Concept Analysis
• Formal Concept Analysis
• Some Computational Problems Related to Pseudo-intents
• COMPUTATIONAL COMPLEXITY OF GENERATORS AND NONGENERATORS IN ALGEBRA

Cites work

• scientific article; zbMATH DE number 3823168 (Why is no real title available?)
• scientific article; zbMATH DE number 3464827 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1249514 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 7635224 (Why is no real title available?)
• scientific article; zbMATH DE number 2246055 (Why is no real title available?)
• Candidate keys for relations
• Comparing performance of algorithms for generating concept lattices
• Concept Lattices
• Formal Concept Analysis
• Formal Concept Analysis
• On computing the size of a lattice and related decision problems
• On generating all maximal independent sets
• On the intractability of computing the Duquenne-Guigues base
• Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
• Subtractive reductions and complete problems for counting complexity classes
• The Complexity of Enumeration and Reliability Problems
• The complexity of computing the permanent
• Two basic algorithms in concept analysis

Cited in

(12)

• Interactive search by using minimal generators
• Introducing the closure structure and the GDPM algorithm for mining and understanding a tabular dataset
• scientific article; zbMATH DE number 2246055 (Why is no real title available?)
• On a complete set of generators for dot-depth two
• NP-completeness of small conflict set generation for congruence closure
• Some complexity results about essential closed sets
• Formal Concept Analysis
• LoCo—A Logic for Configuration Problems
• Closure via functional dependence simplification
• A Polynomial-Time Algorithm to Check Closedness of Simple Second Order Mixed-Integer Sets
• Formal Concept Analysis
• Unique key Horn functions

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

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