Re: Minimal Representation of a Set

I should use "shortest" instead of "minimal" since "minimal" could mean
lexicographically smallest.

Other related problems include:

Shortest representation of an integer/real number in terms of some
given numbers and operations;
Shortest representation of a string in terms of some given strings and
"insert_substring", "delete_substring" operations.


yaoziyuan@xxxxxxxxx wrote:
Suppose there is a set T={e1, e2, e3, ..., e_n}, and some subsets S1,
S3, S3, ..., S_m of T.

Now given another subset Q of T, I want you to represent Q in terms of
S1...S_m and (1) set union operations disallowing overlapping (the two
additive sets should not have common elements) ; (2) set union
operations allowing overlapping; (3) set union operations disallowing
overlapping, and A/B set subtraction operations requiring B be a subset
of A; (4) set union operations allowing overlapping, and A/B set
subtraction operations not requiring B be a subset of A.

Terms (S1, S2, ..., S_m) used in your representation should be as few
as possible.

Regards,
Yao Ziyuan

.