翻訳と辞書
Words near each other
・ "O" Is for Outlaw
・ "O"-Jung.Ban.Hap.
・ "Ode-to-Napoleon" hexachord
・ "Oh Yeah!" Live
・ "Our Contemporary" regional art exhibition (Leningrad, 1975)
・ "P" Is for Peril
・ "Pimpernel" Smith
・ "Polish death camp" controversy
・ "Pro knigi" ("About books")
・ "Prosopa" Greek Television Awards
・ "Pussy Cats" Starring the Walkmen
・ "Q" Is for Quarry
・ "R" Is for Ricochet
・ "R" The King (2016 film)
・ "Rags" Ragland
・ ! (album)
・ ! (disambiguation)
・ !!
・ !!!
・ !!! (album)
・ !!Destroy-Oh-Boy!!
・ !Action Pact!
・ !Arriba! La Pachanga
・ !Hero
・ !Hero (album)
・ !Kung language
・ !Oka Tokat
・ !PAUS3
・ !T.O.O.H.!
・ !Women Art Revolution


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

antimatroid : ウィキペディア英語版
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;〔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」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.