Antimatroid - Paths and Basic Words

Paths and Basic Words

In the set theoretic axiomatization of an antimatroid there are certain special sets called paths that determine the whole antimatroid, in the sense that the sets of the antimatroid are exactly the unions of paths. If S is any feasible set of the antimatroid, an element x that can be removed from S to form another feasible set is called an endpoint of S, and a feasible set that has only one endpoint is called a path of the antimatroid. The family of paths can be partially ordered by set inclusion, forming the path poset of the antimatroid.

For every feasible set S in the antimatroid, and every element x of S, one may find a path subset of S for which x is an endpoint: to do so, remove one at a time elements other than x until no such removal leaves a feasible subset. Therefore, each feasible set in an antimatroid is the union of its path subsets. If S is not a path, each subset in this union is a proper subset of S. But, if S is itself a path with endpoint x, each proper subset of S that belongs to the antimatroid excludes x. Therefore, the paths of an antimatroid are exactly the sets that do not equal the unions of their proper subsets in the antimatroid. Equivalently, a given family of sets P forms the set of paths of an antimatroid if and only if, for each S in P, the union of subsets of S in P has one fewer element than S itself. If so, F itself is the family of unions of subsets of P.

In the formal language formalization of an antimatroid we may also identify a subset of words that determine the whole language, the basic words. The longest strings in L are called basic words; each basic word forms a permutation of the whole alphabet. For instance, the basic words of a poset antimatroid are the linear extensions of the given partial order. If B is the set of basic words, L can be defined from B as the set of prefixes of words in B. It is often convenient to define antimatroids from basic words in this way, but it is not straightforward to write an axiomatic definition of antimatroids in terms of their basic words.

Read more about this topic:  Antimatroid

Famous quotes containing the words paths, basic and/or words:

    “If this be love, to clothe me with dark thoughts,
    Haunting untrodden paths to wail apart;
    My pleasures horror, music tragic notes,
    Tears in mine eyes and sorrow at my heart.
    If this be love, to live a living death,
    Then do I love and draw this weary breath.”
    —Samuel Daniel (1562–1619)

    “There’s one basic rule you should remember about development charts that will save you countless hours of worry.... The fact that a child passes through a particular developmental stage is always more important than the age of that child when he or she does it. In the long run, it really doesn’t matter whether you learn to walk at ten months or fifteen months—as long as you learn how to walk.”
    —Lawrence Kutner (20th century)

    “My words fly up, my thoughts remain below:
    Words without thoughts never to heaven go.”
    —William Shakespeare (1564–1616)