|
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;〔Two early references are and ; Jamison was the first to use the term "antimatroid". surveys the history of rediscovery of antimatroids.〕 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. == Definitions == An antimatroid can be defined as a finite family ''F'' of sets, called ''feasible sets'', with the following two properties: * The union of any two feasible sets is also feasible. That is, ''F'' is closed under unions. * If ''S'' is a nonempty feasible set, then there exists some ''x'' in ''S'' such that ''S'' \ (the set formed by removing ''x'' from ''S'') is also feasible. That is, ''F'' 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 language ''L'' defining an antimatroid must satisfy the following properties: * Every symbol of the alphabet occurs in at least one word of ''L''. * Each word of ''L'' contains at most one copy of any symbol. * Every prefix of a string in ''L'' is also in ''L''. * If ''s'' and ''t'' are strings in ''L'', and ''s'' contains at least one symbol that is not in ''t'', then there is a symbol ''x'' in ''s'' such that ''tx'' is another string in ''L''. 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.〔Korte et al., Theorem 1.4.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「antimatroid」の詳細全文を読む スポンサード リンク
|