The Prime Stems of Rooted Circuits of Closure Spaces and Minimum Implicational Bases
Open Access
- 7 January 2013
- journal article
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 20 (1) , P22
Abstract
A rooted circuit is firstly introduced for convex geometries (antimatroids). We generalize it for closure systems or equivalently for closure operators. A rooted circuit is a specific type of a pair $(X,e)$ of a subset $X$, called a stem, and an element $e\not\in X$, called a root. We introduce a notion called a 'prime stem', which plays the key role in this article. Every prime stem is shown to be a pseudo-closed set of an implicational system. If the sizes of stems are all the same, the stems are all pseudo-closed sets, and they give rise to a canonical minimum implicational basis. For an affine convex geometry, the prime stems determine a canonical minimum basis, and furthermore gives rise to an optimal basis. A 'critical rooted circuit' is a special case of a rooted circuit defined for an antimatroid. As a precedence structure, 'critical rooted circuits' are necessary and sufficient to fix an antimatroid whereas critical rooted circuits are not necessarily sufficient to restore the original antimatroid as an implicational system. It is shown through an example.
Keywords
This publication has 8 references indexed in Scilit:
- Ordered direct implicational basis of a finite closure systemDiscrete Applied Mathematics, 2013
- The multiple facets of the canonical direct unit implicational basisTheoretical Computer Science, 2010
- On the NBC-complexes and -invariants of abstract convex geometriesDiscrete Applied Mathematics, 2009
- The lattices of closure systems, closure operators, and implicational systems on a finite set: a surveyDiscrete Applied Mathematics, 2003
- Closure Spaces and Logic1996
- A circuit set characterization of antimatroidsJournal of Combinatorial Theory, Series B, 1987
- Computing the minimum cover of functional dependenciesInformation Processing Letters, 1986
- Minimum Covers in Relational Database ModelJournal of the ACM, 1980