On formal concepts of random formal contexts
arXiv:2101.11023v14 citations
Originality Incremental advance
AI Analysis
This work addresses a theoretical problem in formal concept analysis for researchers, providing an average-case analysis that is incremental to worst-case studies.
The paper tackles the problem of analyzing the average number of formal concepts in formal concept analysis by introducing a probabilistic model for random formal contexts, proving that the average number has a superpolynomial asymptotic lower bound.
In formal concept analysis, it is well-known that the number of formal concepts can be exponential in the worst case. To analyze the average case, we introduce a probabilistic model for random formal contexts and prove that the average number of formal concepts has a superpolynomial asymptotic lower bound.