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
    0 references
    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

    Identifiers