Value Mapping Sets Sample Clauses

Value Mapping Sets. A Value Mapping Set VMap is defined in terms of sets Domain and Value as the set of all surjective mappings from subsets of Domain to values on Value or to Nil / Value. That is, a value mapping (v : D R) VMap has as domain D Domain and as range R Value Nil , such that all values in the range are mapped from some value in the do- main. Let be a mapping with empty domain and range. ⊆ ∪ { } → ∈ ⊆ ∈ ⊥ ⊥ is clearly an element of every value mapping set. • { ›→ } { } → { } We represent a v-map v : a b , with domain and range of cardinality one, simply as a b . We refer to such v-maps as s-maps, short for “single maps”. We also define the operator, which extends a v-map with an s-map as follows, where v is a v-map, s is an s-map, and Dom(v ) is the domain of v-map v : v • s = w , such that – Dom(w ) = Dom(v ) ∪ Dom(s), – ∀e ∈ Dom(v ), w (e) = v (e), and – ∀e ∈ Dom(s) \ Dom(v ), w (e) = s(e). • • ± ± Although described for a v-map and an s-map, the operator naturally works for any two v-maps. One can think of extending a v-map v with another v-map w as the recursive extension of v with the s-maps that form w . We say that v-map v is a prefix of v-map w and that w extends v (v w ) iff there exists a v-map σ such that v σ = w . Therefore, is a partial order relation on v-map sets. ± H ± ± ± H ∈ ∩ ∈ H H H{ } H ± Given a v-map set V , we say that v-map v is a lower bound of V iff v w for all w in V . A greatest lower bound (glb) of V is a lower bound v of V such that w v for every lower bound w of V , and we represent it by V . Similarly, we say that v is an upper bound of V iff w v for all w in V . A least upper bound (lub) of V is an upper bound v of V such that v w for every upper bound w of V , and we represent it by V . For simplicity of notation, we use v w and v w to represent v, w and v, w , respectively. A set V of v-maps is compatible iff for every pair of v-maps v, w V , for all elements e Dom(v ) Dom(w ), v (e) = w (e). Note that, since is a reflexive partial order on the set of v-maps, if a glb or lub of V exists, then it is unique, and that the existence of the lub V of a set of v-maps V depends on V being compatible. Other than the aforementioned single maps, two other v-maps are of special interest: complete and trivial. Com- plete v-maps are those whose domain equals the respec- tive Domain set; complete v-maps cannot be extended, hence the name. Trivial v-maps are complete v-maps whose ranges equal {Nil }.