On the Complexity of Computing Generators of Closed Sets

DOI10.1007/978-3-540-78137-0_12MaRDI QIDQ5445331zbMATH OpenOpenAlexFDO

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)

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

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)