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. The axioms defining antimatroids as set systems are very similar to those of matroids, but whereas matroids are defined by an exchange axiom, 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 of finite sets, called feasible sets, with the following two properties: The union of any two feasible sets is also feasible. That is, is closed under unions. If is a nonempty feasible set, then contains an element for which (the set formed by removing from ) is also feasible. That is, is an accessible set system. 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 string that belongs to this set is called a word of the language. A language defining an antimatroid must satisfy the following properties: Every symbol of the alphabet occurs in at least one word of .