The prime stems of rooted circuits of closure spaces and minimum implicational bases (Q1953403)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The prime stems of rooted circuits of closure spaces and minimum implicational bases |
scientific article |
Statements
The prime stems of rooted circuits of closure spaces and minimum implicational bases (English)
0 references
7 June 2013
0 references
Summary: 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. This is shown through an example.
0 references
closure system
0 references
closure operator
0 references
Armstrong's axioms
0 references
pseudo-closed set
0 references
convex geometry
0 references
rooted circuit
0 references
precedence structure
0 references
antimatroid
0 references