Geodesic
Decomposition of underdetermined data
Diskretnyj analiz i issledovanie operacij, Tome 19 (2012) no. 6, pp. 72-98.

Voir la notice de l'article provenant de la source Math-Net.Ru

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, lower approximation
Mots-clés : information equivalence, decomposition, polynomial algorithm. 
@article{DA_2012_19_6_a6,
     author = {L. A. Sholomov},
     title = {Decomposition of underdetermined data},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {72--98},
     publisher = {mathdoc},
     volume = {19},
     number = {6},
     year = {2012},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2012_19_6_a6/}
}
TY  - JOUR
AU  - L. A. Sholomov
TI  - Decomposition of underdetermined data
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2012
SP  - 72
EP  - 98
VL  - 19
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2012_19_6_a6/
LA  - ru
ID  - DA_2012_19_6_a6
ER  - 
%0 Journal Article
%A L. A. Sholomov
%T Decomposition of underdetermined data
%J Diskretnyj analiz i issledovanie operacij
%D 2012
%P 72-98
%V 19
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2012_19_6_a6/
%G ru
%F DA_2012_19_6_a6
L. A. Sholomov. Decomposition of underdetermined data. Diskretnyj analiz i issledovanie operacij, Tome 19 (2012) no. 6, pp. 72-98. http://geodesic.mathdoc.fr/item/DA_2012_19_6_a6/

[1] Agibalov G. P., Konechnye avtomaty na polureshetkakh, Izd-vo TGU, Tomsk, 1993, 209 pp. | Zbl

[2] Gallager R., Teoriya informatsii i nadezhnaya svyaz, Sov. radio, M., 1974, 720 pp. | Zbl

[3] Parvatov N. G., “Funktsionalnaya polnota v zamknutykh klassakh kvazimonotonnykh i monotonnykh trëkhznachnykh funktsii na polureshëtke”, Diskret. analiz i issled. operatsii. Ser. 1, 10:1 (2003), 61–78 | MR | Zbl

[4] Parvatov N. G., “O formakh predstavleniya monotonnykh i kvazimonotonnykh funktsii na trekhelementnoi polureshetke”, Mat. IX Mezhdunar. seminara “Diskretnaya matematika i eë prilozheniya”, Izd-vo mekh.-mat. f-ta MGU, M., 2007, 127–130

[5] Sholomov L. A., “Preobrazovanie nechëtkikh dannykh s sokhraneniem informatsionnykh svoistv”, Diskret. analiz i issled. operatsii. Ser. 1, 12:3 (2005), 85–104 | MR | Zbl

[6] Sholomov L. A., “Elementy teorii nedoopredelënnoi informatsii”, Prikl. diskret. matematika, 2009, Pril. No 2, 18–42

[7] Sholomov L. A., “Dekompozitsiya nedoopredelënnykh dannykh”, Mat. XVI Mezhdunar. konf. “Problemy teoreticheskoi kibernetiki”, Izd-vo Nizhegorodskogo gos. un-ta, Nizhnii Novgorod, 2011, 570–573

[8] Yablonskii S. V., Elementy matematicheskoi kibernetiki, Vyssh. shk., M., 2007, 188 pp.