Geodesic
Matrices and graphs of essential dependence of proper families of functions
Fundamentalʹnaâ i prikladnaâ matematika, Tome 14 (2008) no. 4, pp. 137-149 
A. A. Kozlov; V. A. Nosov; A. E. Pankratiev. Matrices and graphs of essential dependence of proper families of functions. Fundamentalʹnaâ i prikladnaâ matematika, Tome 14 (2008) no. 4, pp. 137-149. http://geodesic.mathdoc.fr/item/FPM_2008_14_4_a8/
@article{FPM_2008_14_4_a8,
     author = {A. A. Kozlov and V. A. Nosov and A. E. Pankratiev},
     title = {Matrices and graphs of essential dependence of proper families of functions},
     journal = {Fundamentalʹna\^a i prikladna\^a matematika},
     pages = {137--149},
     year = {2008},
     volume = {14},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/FPM_2008_14_4_a8/}
}
TY  - JOUR
AU  - A. A. Kozlov
AU  - V. A. Nosov
AU  - A. E. Pankratiev
TI  - Matrices and graphs of essential dependence of proper families of functions
JO  - Fundamentalʹnaâ i prikladnaâ matematika
PY  - 2008
SP  - 137
EP  - 149
VL  - 14
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/FPM_2008_14_4_a8/
LA  - ru
ID  - FPM_2008_14_4_a8
ER  - 
%0 Journal Article
%A A. A. Kozlov
%A V. A. Nosov
%A A. E. Pankratiev
%T Matrices and graphs of essential dependence of proper families of functions
%J Fundamentalʹnaâ i prikladnaâ matematika
%D 2008
%P 137-149
%V 14
%N 4
%U http://geodesic.mathdoc.fr/item/FPM_2008_14_4_a8/
%G ru
%F FPM_2008_14_4_a8

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

This paper considers proper families of functions, which are used in functional specification of Latin squares of large size over the set of $n$-dimensional binary vectors. Proper families of functions are studied from the viewpoint of the intrinsic structure of the corresponding graphs of essential dependence and their adjacency matrices. Various necessary and sufficient conditions for a binary matrix to be treated as the adjacency matrix of the graph of essential dependence of a proper family of functions are derived. Also, transformations of matrices are considered, under which the indicated property is preserved. It is demonstrated that any directed graph without loops and multiple edges can be embedded as an induced subgraph into the graph of essential dependence of some proper family of functions. Moreover, such embedding is reasonably economical and the functions of the resulting proper family inherit properties of the functions that realize the original graph as the graph of essential dependence.

[1] Kloss B. M., Malyshev V. A., “Opredelenie regulyarnosti avtomata po ego kanonicheskim uravneniyam”, DAN SSSR, 172:3 (1967), 543–546 | MR | Zbl

[2] Nosov V. A., “Kriterii regulyarnosti bulevskogo neavtonomnogo avtomata s razdelënnym vkhodom”, Intellekt. sist., 3:3–4 (1998), 269–280

[3] Nosov V. A., “O postroenii klassov latinskikh kvadratov v bulevoi baze dannykh”, Intellekt. sist., 4:3–4 (1999), 307–320

[4] Nosov V. A., “Postroenie parametricheskogo semeistva latinskikh kvadratov v vektornoi baze dannykh”, Intellekt. sist., 8:1–4 (2004), 517–528

[5] Nosov V. A., Pankratev A. E., “Latinskie kvadraty nad abelevymi gruppami”, Fundament. i prikl. mat., 12:3 (2006), 65–71 | MR

[6] Nosov V. A., Pankratev A. E., “O semeistvakh funktsii, zadayuschikh latinskie kvadraty nad abelevymi gruppami”, Vestn. Mosk. gos. un-ta lesa. Lesnoi vestnik, 2007, no. 2(51), 141–144

[7] Primenko E. A., Skvortsov E. F., “Ob usloviyakh regulyarnosti konechnykh avtonomnykh avtomatov”, Diskret. mat., 2:1 (1990), 26–30 | MR | Zbl

[8] Shennon K., “Teoriya svyazi v sekretnykh sistemakh”, Raboty po teorii informatsii i kibernetike, M., 1963, 333–369

[9] Denes J., Keedwell A. D., Latin Squares and Their Applications, Budapest, 1974 | MR | Zbl