Geodesic
About primitive systems of natural numbers
Prikladnaâ diskretnaâ matematika, no. 2 (2012), pp. 5-14
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The set structure of primitive systems of natural numbers is described, and the main properties of such systems are installed. An algorithm for enumerating primitive systems of numbers not exceeding a given number $m$ is constructed using the concepts of deadlockness and $k$-minimalities of primitive systems. Also, some algorithms are offered for determining the primitiveness index of a finite directed graph by means of depth-first search and the exponentiation of the vertex adjacency matrix. Computational complexity of the algorithms is estimated.
Keywords: primitive system of natural numbers, primitive graph, exponent
Mots-clés : primitive matrix, subexponent. 
@article{PDM_2012_2_a0,
     author = {S. N. Kjazhin and V. M. Fomichev},
     title = {About primitive systems of natural numbers},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {5--14},
     year = {2012},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2012_2_a0/}
}
TY  - JOUR
AU  - S. N. Kjazhin
AU  - V. M. Fomichev
TI  - About primitive systems of natural numbers
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2012
SP  - 5
EP  - 14
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/PDM_2012_2_a0/
LA  - ru
ID  - PDM_2012_2_a0
ER  - 
%0 Journal Article
%A S. N. Kjazhin
%A V. M. Fomichev
%T About primitive systems of natural numbers
%J Prikladnaâ diskretnaâ matematika
%D 2012
%P 5-14
%N 2
%U http://geodesic.mathdoc.fr/item/PDM_2012_2_a0/
%G ru
%F PDM_2012_2_a0
S. N. Kjazhin; V. M. Fomichev. About primitive systems of natural numbers. Prikladnaâ diskretnaâ matematika, no. 2 (2012), pp. 5-14. http://geodesic.mathdoc.fr/item/PDM_2012_2_a0/

[1] Fomichev V. M., “Otsenki eksponentov primitivnykh grafov”, Prikladnaya diskretnaya matematika, 2011, no. 2(11), 101–112

[2] Sachkov V. N., Tarakanov V. E., Kombinatorika neotritsatelnykh matrits, TVP, M., 2000 | MR | Zbl

[3] Birkgof G., Teoriya reshetok, Nauka, M., 1984 | MR

[4] Arnold V. I., Eksperimentalnoe nablyudenie matematicheskikh faktov, MTsNMO, M., 2006

[5] Koblits N., Kurs teorii chisel i kriptografii, TVP, M., 2001

[6] Rosser B., “The $n$-th prime is greater than $n\log n$”, Proc. London Math. Soc., 45 (1939), 21–44 | DOI | MR

[7] Lakhno A. P., “Poisk v glubinu i ego primenenie”, Moskovskie olimpiady po informatike, MTsNMO, M., 2006

[8] Porublev I. N., Stavrovskii A. B., Algoritmy i programmy. Reshenie olimpiadnykh zadach, Vilyams, M., 2007

[9] Wielandt H., “Unzerlegbare nicht negative Matrizen”, Math. Zeitschr., 52 (1950), 642–648 | DOI | MR | Zbl

[10] Sachkov V. N., Oshkin I. B., “Eksponenty klassov neotritsatelnykh matrits”, Diskretnaya matematika, 5:2 (1993), 150–159 | MR | Zbl