Volume 19, No 6, 2012, P. 72-98

UDC 519.728
L. A. Sholomov 
Decomposition of underdetermined data

Abstract:
For any underdetermined source in general form, we consider its decomposition as product of sources generating symbols 0, 1, and the indefinite symbol *. Also, we learn best approximate (in a prescribed sense) decomposition if correct decomposition is impossible. It is proved that the best approximate decomposition always exists and is unique up to some equivalence (for the decomposable source, it coincides with its decomposition). A polynomial algorithm to construct the approximate decomposition is proposed. Several problems related to simplifications and equivalent transformations of decompositions are studied. For them, some polynomial algorithms are proposed.
Tabl. 4, bibliogr. 8.

Keywords: underdetermined source, information equivalence, decomposition, lower approximation, polynomial algorithm.

Sholomov Lev Abramovich ¹
1. Institute of System Analysis RAS,
9 60-letiya Oktyabrya ave., 117312 Moscow, Russia
e-mail: sholomov@isa.ru