Antimatroid

In mathematics, an antimatroid is a formal system that describes processes in which a set is built up by including elements one at a time, and in which an element, once available for inclusion, remains available until it is included. Antimatroids are commonly axiomatized in two equivalent ways, either as a set system modeling the possible states of such a process, or as a formal language modeling the different sequences in which elements may be included.Dilworth (1940) was the first to study antimatroids, using yet another axiomatization based on lattice theory, and they have been frequently rediscovered in other contexts; see Korte et al. (1991) for a comprehensive survey of antimatroid theory with many additional references. In mathematics, an antimatroid is a formal system that describes processes in which a set is built up by including elements one at a time, and in which an element, once available for inclusion, remains available until it is included. Antimatroids are commonly axiomatized in two equivalent ways, either as a set system modeling the possible states of such a process, or as a formal language modeling the different sequences in which elements may be included.Dilworth (1940) was the first to study antimatroids, using yet another axiomatization based on lattice theory, and they have been frequently rediscovered in other contexts; see Korte et al. (1991) for a comprehensive survey of antimatroid theory with many additional references. The axioms defining antimatroids as set systems are very similar to those of matroids, but whereas matroids are defined by an exchange axiom (e.g., the basis exchange, or independent set exchange axioms), antimatroids are defined instead by an anti-exchange axiom, from which their name derives.Antimatroids can be viewed as a special case of greedoids and of semimodular lattices, and as a generalization of partial orders and of distributive lattices. Antimatroids are equivalent, by complementation, to convex geometries, a combinatorial abstraction of convex sets in geometry. Antimatroids have been applied to model precedence constraints in scheduling problems, potential event sequences in simulations, task planning in artificial intelligence, and the states of knowledge of human learners. An antimatroid can be defined as a finite family F of sets, called feasible sets, with the following two properties: Antimatroids also have an equivalent definition as a formal language, that is, as a set of strings defined from a finite alphabet of symbols. A language L defining an antimatroid must satisfy the following properties: If L is an antimatroid defined as a formal language, then the sets of symbols in strings of L form an accessible union-closed set system. In the other direction, if F is an accessible union-closed set system, and L is the language of strings s with the property that the set of symbols in each prefix of s is feasible, then L defines an antimatroid. Thus, these two definitions lead to mathematically equivalent classes of objects. 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.