Antimatroid - Definitions

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 \ {x} (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.