Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.intsys.msu.ru/magazine/archive/v11(1-4)/samonenko-787-792.pdf Дата изменения: Mon Feb 18 14:25:28 2008 Дата индексирования: Tue Oct 2 00:23:48 2012 Кодировка:

r-
. .

r- . r- c . r- .

1. r-
A = (A, Q, ) A, Q : Q в A Q. 1. A r -, f : Qr+1 Q q1 , . . . , qr Q, A q Q, (q , ) = f (q , (q1 , ), . . . , (qr , )). q1 , . . . , qr , f . , r -, r q1 , . . . , qr Q, , , A , ( f ), q Q . P R(n, r ) r - n . K (n) n . 1. n P R(n, 1) P R(n, 2) ··· 2, P R(n, n - 1) P R(n, n - 1) = K (n)


788

. .

A = (A, Q, ) . A : Q Q : (q ) = (q , ) A H (A) = (A , ·). A , , , . , ( ), H (A). H (A)/ A , A S Gr (A). , S Gr (A) (). 2. A P R(n, r ) \ P R(n, r - 1), |S Gr (A)| n
r

A , r |S Gr (A)|.

, r -. 3. A = (A, Q, ) P r (n, r ) , q 1 , . . . , qr Q : , A , (qi , ) = (qi , ), i = 1, . . . , r , , q Q (q , ) = (q , ). . 4. A = (A, Q, ) P r (n, r ) , q 1 , . . . , qr Q : Q , (q i , ) = qi , i = 1, . . . , r , , q Q (q , ) = q . A A = (A, Q, ), q f Q, q Q (q .) = qf . , .


r-

789

A = (A, Q, ) K (n) n . , A (n - 1) 2 [3]. . 3- n 6 n [2]. 5. A = (A, Q, ) P r (n, r ) , r(r-1)(r-2) + n. 6

2.
G = (V , E , ) V , E : E V в V , ( ). O ut(v ) v , O ut(v ) = {e E |v V : (v , v ) = e}. Ov = |O ut(v )| , v . G E : E N, , v V , E O ut(v ) {1, . . . , O v }. , v , E . E , : V в N V , v V e O ut(v ), (v , (v , E (e))) = e. (v , t) , t v . Q F(Q) = {f : Q s Q| s N0 } Q s Q. G Q, V : V F(Q), v V V (v ) Ov . R = (Q, G, E , V ), Q , G = (V , E , )


790

. .

, E G, V G Q. , Q V AN et(Q, V ). V = {1, . . . , n} G. C R = (Q, G, E , V ) : Qn Qn : R (q1 , . . . , qr ) = (f1 (q
(1,1)

,...,q

(1,O1 )

), . . . , fn (q

(n,1)

,...,q

(n,On ))

),

fi = V (i), i = 1, . . . , n. N = (A, Q, V , ), A , Q , V , : A AN et(Q, V ) , . N = (A, Q, V , ) A = A(N) = (A, Qn , ), n = |V | : (a, (q1 , . . . , qn )) =
(a)

(q1 , . . . , qn )

. V , Q . a A (a) v V V (v ). , O ut(v ) G (a). , . .

3. r-
r - , . .


r-

791

d1 , . . . , dk N, k - d1 , . . . , dk , V = Ed1 в · · · в Edk . G . u1 , . . . , us Zk . v = (l1 , . . . , lk ) V s (v + u1 ) mod (d1 , . . . , dk ), . . . , (v + u1 ) mod (d1 , . . . , dk ), (a1 , . . . , ak ) mod (d1 , . . . , dk ) = (a1 mod d1 , . . . , ak mod dk ). G = G(V ; u 1 , . . . , uk ) . E : e E v (v + u i ) mod (d1 , . . . , dk ), E (e) = i. : Q k Q, V (v ) = . R = (Q, G(E d1 в · · · в Edk ; u1 , . . . , us ), E , ), E . H AN et(Q; d1 , . . . , dk ) Q Ed1 в · · · в Edk . d 1 в · · · в dk N = (A, Q, V , ), : A H AN et(Q; d 1 , . . . , dk ). 6. N = (A, Q, V , ) d1 в · · · в dk , A(N) P R(n, r (n)), n = |Q|d1 ...dk r (n) log n (n) d1 , . . . , dk .
|Q|

R = (Q, G(V , E , ), E , V ) . R h : V V , : 1) v1 , v2 V , , e E , (e) = (v1 , v2 ), , e E , (e ) = (h(v1 ), h(v2 )) E (e) = E (e ). , v1 v2 e, e , h(v1 ) h(v2 ), . 2) v V , V (h(v )) = V (v ). , h .


792

. .

R E nd(R). E nd(R) . N = (A, Q, V , ) . N E nd(N) =
aA

(E nd( (a)))

V = 1, . . . , n h : V V , h h : Qn Qn : h(q1 , . . . , qn ) = (q
h(1)

,...,q

h(n)

)

, h E nd(N) h A(N) . Q Qn A(N) , q Q n q Q h E nd(N), q = h(q ). 7. N = (A, Q, V , ) Q A(N), A(N) P R(n, |Q |).

4.
.


[1] . ., . ., . . . .: , 1985. [2] . ., . ., . . , // . 1987. 2. [3] C erny J. Poznamka k homogennym eksp erimentom s konechnymi automatami // Math.-Fiz. Cas. 14 (1964).