File closed-set.hh¶
Definition of a downward and upward closed set.
This file contains definition of a closed set and function which allow us to work with them (membership, inclusion, union, intersection)
Description: In this context, an upward-closed set is a set of sets of elements of type T, (set of nodes of type T, where a node is a set of elements of type T) where the elements come from the discrete range <min_val; max_val>. If the upward closed set contains a subset A of the range <min_val; max_val>, it also contains all the supersets of A (in context of the discrete range <min_val; max_val>). Thus, the upward closed set could be easily represented by its 1) type (upward closed), 2) discrete range borders (min_val, max_val), 3) its antichain. Analogously, a downward closed set contains all the subsets of the antichain elements.
It is possible to:
-> ==- and !=-compare two closed sets -> <=- and >=-compare two closed sets of the same type -> get a text representation of the closed set -> chceck whether the closed set contains a given node/nodes -> insert a node/more nodes to the closed set -> perform an union over two closed sets of the same type and with the same carrier -> perform an intersection over two closed sets of the same type and with the same carrier -> compute a complement of a closed set
It is not possible to:
-> choose a custom carrier which is not a discrete range <min_val; max_val> -> <=- and >=-compare two closed sets of the different types (nonsense) -> remove a node/more nodes from the closed set (nonsense) -> perform an union over two closed sets of different types or different carriers (nonsense) -> perform an intersection over two closed sets of different types or different carriers (nonsense)
Examples:
Let us have the carrier {0, 1, 2, 3} and the upward-closed set with the antichain {{0}, {1, 2}}. We can write↑{{0}, {1, 2}} = {{0}, {0, 1}, {0, 2}, {0, 3}, {0, 1, 2}, {0, 1, 3}, {0, 2, 3}, {1, 2}, {1, 2, 3}, {0, 1, 2, 3}}.
Let us have the carrier {0, 1, 2, 3} and the downward-closed set with the antichain {{0}, {1, 2}}. We can write ↓{{0}, {1, 2}} = {{0}, {1, 2}, {1}, {2}, {}}.
- Author
Tomáš Kocourek
-
namespace mata
Main namespace including structs and algorithms for all automata.
In particular, this includes:
Alphabets,
Formula graphs and nodes,
Closed sets.
-
template<typename T>
struct ClosedSet¶ - #include <closed-set.hh>
Closed set.
Contains discrete range borders, its type and the corresponding anti-chain. It is necessary to be able to evaluate relation operators <, <=, >, >=, ==, != over instances of this datatype T.
- Template Parameters:
T – Datatype the closed set contains.
Public Functions
-
inline ClosedSet()¶
-
inline ClosedSet(const ClosedSetType type, const T &min_val, const T &max_val, const T &value)¶
-
inline ClosedSet(const ClosedSetType type, const T &min_val, const T &max_val, const Node &node)¶
-
inline ClosedSet(const ClosedSetType type, const T &min_val, const T &max_val, const Nodes &antichain = Nodes())¶
-
bool operator==(const ClosedSet &rhs) const = default¶
Two closed sets are equivalent iff their type, borders and corresponding antichains are the same. They are not equivalent otherwise.
-
inline bool is_upward_closed() const¶
-
inline bool is_downward_closed() const¶
-
inline ClosedSetType type()¶
-
inline ClosedSetType type() const¶
-
bool contains(const Node &node) const¶
This function decides whether a set of elements is part of the closed set by subset-comparing the input with all elements of the antichain.
decides whether the closed set contains a given element
- Parameters:
node – a given ordered vector of elements of the type T
- Returns:
true iff the given ordered vector belongs to the current closed set
-
bool contains(const Nodes &nodes) const¶
This function decides whether a set of sets of elements is a part of the closed set by subset-compraring the input with all elements of the antichain.
decides whether the closed set contains a given set of sets of elements
- Parameters:
nodes – a given ordered vector of ordered vectors of elements of the type T
- Returns:
true iff the given ordered vector of ordered vectors belongs to the current closed set
-
bool in_interval(const Node &node) const¶
This function decides whether a given ordered vector of elements of the datatype T belongs to the discrete interval of the current closed set.
decides whether the given vector respects the borders
- Parameters:
node – a given ordered vector of elements of the type T which will be inspected
- Returns:
true iff the given ordered vector respects the borders
-
void insert(const Node &node)¶
Adds a new element to the closed set.
If the element is already contained in the closed set, the closed set remains unchanged. Otherwise, the antichain will be recomputed.
inserts a new element to the closed set
- Parameters:
node – a given node which will be added to the closed set
-
ClosedSet set_union(const ClosedSet &rhs) const¶
Performs a union over two closed sets with the same type and carrier.
This function simply adds all the elements of the antichain of the first closed set to the second closed set
performs a union over closed sets
- Parameters:
rhs – a given closed set which will be united with the current one
- Returns:
a union of the given closed sets
-
ClosedSet intersection(const ClosedSet &rhs) const¶
Performs an intersection over two closed sets with the same type and carrier.
performs an intersection over closed sets
- Parameters:
rhs – a given closed set which will be intersectioned with the current one
- Returns:
an intersection of the given closed sets
-
ClosedSet complement() const¶
Performs a complementation over a closed set.
The result will contain nodes which are not elements of the former closed set. The complement of an upward-closed set is always downward-closed and vice versa.
performs a complementation over a closed set
- Returns:
a complement of a closed set
Private Members
-
ClosedSetType type_ = {ClosedSetType::UpwardClosedSet}¶