Geodesic
On complexity of standard forms for multifunctions
The Bulletin of Irkutsk State University. Series Mathematics, Tome 22 (2017), pp. 63-70 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Consider discrete functions defined on set $A$. In this case we define multifunctions as functions on set $2^A$. Values of a multifunction for inputs equal to one-element sets are given and values for other sets are calculated as a union of values on one-element sets. Superposition of multifunctions is defined in the same way. Multifunction is a generalization of different models of uncertainty, incomplete and partial functions and hyperfunctions. These models can be useful for processing incomplete and contradictional information in intelligent systems. Standard forms representing multifunctions are defined using intersection multifunction. Standard form representation of a multifunction is not unique. It is natural to define complexity of a standard form as the number of its components. This paper introduces exact bounds on complexity of $n$-ary multifunctions and proposes an algorithm for minimization of $4$-argument multifunctions. This paper considers the relationship between multifunctions that have only two output values, and Boolean functions. It is shown that the complexity of the standard forms of any such multifunction coincides with the length of the disjunctive normal form of the corresponding Boolean function. The article gives an upper bound for the complexity of the standard forms of multifunctions, and also introduces a sequence of multifunctions whose complexity coincides with this upper bound. Thus, the complexity of the class of $n$-ary multifunctions is obtained. Also, an algorithm is proposed for minimizing multifunctions of rank $2$, based on a sequential search of formulas of increasing complexity. This algorithm allows us to find the complexities of all $4$-ary multifunctions of rank $2$.
Keywords: multifunction, minimization, complexity, disjunctive normal form. 
@article{IIGUM_2017_22_a4,
     author = {A. S. Kazimirov},
     title = {On complexity of standard forms for multifunctions},
     journal = {The Bulletin of Irkutsk State University. Series Mathematics},
     pages = {63--70},
     year = {2017},
     volume = {22},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IIGUM_2017_22_a4/}
}
TY  - JOUR
AU  - A. S. Kazimirov
TI  - On complexity of standard forms for multifunctions
JO  - The Bulletin of Irkutsk State University. Series Mathematics
PY  - 2017
SP  - 63
EP  - 70
VL  - 22
UR  - http://geodesic.mathdoc.fr/item/IIGUM_2017_22_a4/
LA  - ru
ID  - IIGUM_2017_22_a4
ER  - 
%0 Journal Article
%A A. S. Kazimirov
%T On complexity of standard forms for multifunctions
%J The Bulletin of Irkutsk State University. Series Mathematics
%D 2017
%P 63-70
%V 22
%U http://geodesic.mathdoc.fr/item/IIGUM_2017_22_a4/
%G ru
%F IIGUM_2017_22_a4
A. S. Kazimirov. On complexity of standard forms for multifunctions. The Bulletin of Irkutsk State University. Series Mathematics, Tome 22 (2017), pp. 63-70. http://geodesic.mathdoc.fr/item/IIGUM_2017_22_a4/

[1] Lupanov O. B., “On logic functions realization with formulas of finite classes (of finite depth) in basis of AND, OR, NOT”, Problemy kibernetiki, 6, Fizmatgiz, M., 1961, 5–14 (in Russian) | Zbl

[2] Panteleyev V. I., “Completeness criteria for incompletely defined partial Boolean functions”, Vestn. Novosib. Gos. Univ., Ser. Mat. Mekh. Inform., 9:3 (2009), 95–114 (in Russian) | Zbl

[3] Peryazev N. A., “Clones, co-clones, hyperclones and superclones”, Uchenye zapiski Kazanskogo gosudarstvennogo universiteta. Seriya: Fiziko-matematicheskiye nauki, 151, no. 2, Kazan, 2009, 120–125 (in Russian) | Zbl

[4] Peryazev N. A., Yakovchuk I. A., “Minimization of multioperations in the class of standard forms”, Izv. Irkutsk. Gos. Univ., Ser. Mat., 2:2 (2009), 117–126 (in Russian)

[5] Peryazev N. A., “Standard forms of multioperations in superclones”, Izv. Irkutsk. Gos. Univ., Ser. Mat., 3:4 (2010), 88–95 (in Russian)

[6] Peryazev N. A., “Superclones of multioperations”, Trudy VIII Mezhdunarodnoy konferentsii «Diskretnye sistemy v teorii upravlyayuschih sistem», MAIS Press, M., 2009, 233–238 (in Russian)

[7] Sharankhaev I. K., “On decomposition method for multifunctions”, Diskretnye modeli v teorii upravlyayuschih sistem, IX Mezhdunarodnaya konferentsiya, Trudy, MAKS Press, M., 2015, 266–267 (in Russian)

[8] A. Kazimirov, V. Panteleyev, L. Riabets, S. Vinokurov, “Decision support system based on 4-valued logic with multi-interpretations”, Proceedings of International Conference on Soft Computing and Measurements, SCM 2015 (May 19–21, St. Petersburg, Russia, 2015), 198–199

[9] N. A. Peryazev, I. K. Sharankhaev, “Galois theory for clones and superclones”, Discrete Mathematics and Applications, 26:4 (2016), 227–238 | DOI | MR | Zbl

[10] B. A. Romov, “The completeness problem in partial hyperclones”, Discrete Mathematics, 306 (2006), 1405–1414 | DOI | MR | Zbl

[11] S. Vinokurov, A. Kazimirov, N. Pustovoytov, A. Frantseva, “Decision Support System for Medical Prescriptions Based on 4-Valued Logic”, Proceedings of the XIX International Conference on Soft Computing and Measurement, SCM 2016 (May 25–27, St. Petersburg, Russia), 2016, 307–308