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:
“O Master, let me walk with thee
In lowly paths of service free;
Tell me thy secret; help me bear
The strain of toil, the fret of care;”
—Washington Gladden (1836–1918)
“Scientific reason, with its strict conscience, its lack of prejudice, and its determination to question every result again the moment it might lead to the least intellectual advantage, does in an area of secondary interest what we ought to be doing with the basic questions of life.”
—Robert Musil (1880–1942)
“It is no small mischief to a boy, that many of the best years of his life should be devoted to the learning of what can never be of any real use to any human being. His mind is necessarily rendered frivolous and superficial by the long habit of attaching importance to words instead of things; to sound instead of sense.”
—William Cobbett (1762–1835)