Theoretical Foundations of Applied Discrete Mathematics

Decomposition and approximation of underdetermined data

L. A. Sholomov

Institute of Systems Analysis, Russian Academy of Sciences, Moscow

Abstract: For any underdetermined source, 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. We prove that the best approximate decomposition always exists (for the decomposable source, it coincides with its decomposition), and it may be constructed by a polynomial algorithm. For some problems relating to simplifications and equivalent transformations of decompositions, polynomial algorithms are offered. In closing, we state that any underdetermined source has a decomposition in some more general form.

UDC: 519.816