Minimal representative set for a system of frequency classes of underdetermined words

Let a finite set M and a system T of some non-empty subsets T С M be given. Associated with the sets M and T are the alphabets A₀ = {ai, i G M} of basic symbols and A = {a_T, T G T} of underdeter-mined symbols. The set of all words of length l in the alphabet A, in which each symbol a_T is present r_T times, ^ r_T = l, is called frequency class and denoted by Kj(r) where t er r = (r_T, T G T). The specification of the word v in the alphabet A is any word obtained from v by replacing each symbol a_T with some a_i, i G T. The specification of the set V of words in the alphabet A is any set of words in the alphabet A₀, containing for each word v G V some specification of it. The class (r₁) is considered to be more representative than the class K_l2 (r₂), if l₁ ^ l₂ and, whatever the specification of the class K_1l (r₁), the set of beginnings of the length l₂ of all words from the specification forms some specification for the class K_l2(r₂). Let K be some system of frequency classes. A subsystem of K is called a representative set of the system K if, for any Kj(r) G K, the subsystem contains a class that is more representative than Kj(r). The paper presents a method for finding the smallest representative set for an arbitrary system of frequency classes. This setting arises in the problems of underdetermined data compression and of underdetermined functions implementation.

Keywords

Authors

References