Skip to Main content Skip to Navigation
Book sections

Enumerating Maximal Consistent Closed Sets in Closure Systems

Abstract : Given an implicational base, a well-known representation for a closure system, an inconsistency binary relation over a finite set, we are interested in the problem of enumerating all maximal consistent closed sets (denoted by MCCEnum for short). We show that MCCEnum cannot be solved in output-polynomial time unless P = NP, even for lower bounded lattices. We give an incremental-polynomial time algorithm to solve MCCEnum for closure systems with constant Carathéodory number. Finally we prove that in biatomic atomistic closure systems MCCEnum can be solved in output-quasipolynomial time if minimal generators obey an independence condition, which holds in atomistic modular lattices. For closure systems closed under union (i.e., distributive), MCCEnum is solved by a polynomial delay algorithm [22, 25].
Document type :
Book sections
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03354969
Contributor : Simon Vilmin Connect in order to contact the contributor
Submitted on : Monday, September 27, 2021 - 8:28:04 AM
Last modification on : Thursday, October 21, 2021 - 3:33:41 AM

File

2102.04245.pdf
Files produced by the author(s)

Identifiers

Citation

Lhouari Nourine, Simon Vilmin. Enumerating Maximal Consistent Closed Sets in Closure Systems. Formal Concept Analysis. ICFCA 2021, 12733, pp.57-73, 2021, Lecture Notes in Computer Science, ⟨10.1007/978-3-030-77867-5_4⟩. ⟨hal-03354969⟩

Share

Metrics

Record views

30

Files downloads

26