On the Complexity of Computing Generators of Closed Sets

DOI10.1007/978-3-540-78137-0_12zbMATH Open1131.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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Knowledge representation (68T30) Database theory (68P15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Comparing performance of algorithms for generating concept lattices
• The complexity of computing the permanent
• The Complexity of Enumeration and Reliability Problems
• Candidate keys for relations
• Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
• Subtractive reductions and complete problems for counting complexity classes
• Concept Lattices
• On generating all maximal independent sets
• Two Basic Algorithms in Concept Analysis
• On computing the size of a lattice and related decision problems
• Formal Concept Analysis
• Formal Concept Analysis

Cited In (7)

• 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
• 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
• Unique key Horn functions
• NP-completeness of small conflict set generation for congruence closure

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)