Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.intsys.msu.ru/magazine/archive/v9(1-4)/kirnasov-433-444.pdf Дата изменения: Tue May 9 23:21:20 2006 Дата индексирования: Tue Oct 2 00:07:19 2012 Кодировка: ISO8859-5

. .

. n n , n n .

1.
A = (A, Q, B , , ). A , Q , , , , , v : v , v , 1) q Qv , q = (q , v ), e = (v w), v w , q = e (q , v ) Qw , Qv Qw , v w , e , e;


434

. .

2) e = (v w) , v w, Qw = q Qw c q Qv , (q , v ) = q [1]. E . , , E , , . E l(E ). A l(A). , l(A) = 0. [1], . A A , , q1 , q2 Q : (q1 , ) = (q2 , ), (q1 , ) = (q2 , ). A. A l u (A). A , lu (A) = 0. [2], , . , . , . .

2.
Km,n,k 0 m , n k . K m,n,k -




435

m , n k . Kn n . A. l(A) A, l u (A) A. (A) = lu((A) . l A) (n) = max (A).
AK
n

: 1.
n 4

(n)

n.

2. m 2, k 2 n , C > 15 A K m,n,k (A) C .

3. 1
. A = (A, Q, B , , ) Kn E l0 . l0 n, A. , , 1. . ES S Q A, A , ES S . , E A E S S A. , . Si , S0 = Q. i- ESi , , , E A. z E Si . A


436

. .

qz . , z , , . i . , l0 . Si+1 i : Si+1 = {q Q|q S : (q , ) = q } \ {qz }. , , i S , q z , (qz , ) = qz , , |Si | - |Si+1 | 1. |S0 | = n, n Sj |Sj | = 1. i , . . , , l0 n. , A. i i i . , , i , , , , Si+1 . , , . , i , , , i+1 , , S i+1 . , i+1 , i+1 , i qz+1 , Si+2 . . , , A, 1. . n. n . n = 2k . A = (A, Q, B , , ). A = {a0 , a1 , a2 , . . . , ak }, B = {b1 , b2 , . . . , bk }, Q = {q1 , q2 , . . . , qn }. :




437

(q (qi , a0 ) = (qi , as ) = (qi , as ) =

i

, aj ) = qi i, j ; i = 2j i = 2j - 1, i = 2s, i = 2s - 1.

bj , b1 , b2 ,

, A l(A) = 2, l u (A) = k + 1, k n (A) 2 = 4 , . 1.

4. 2
. A = (A, Q, B , , ). |B | = k . k - , A, B , A, : V (E ) 2E , (E , ) A. m k Dm,k . D m,k . E . : 1. A E , l, A , l. , D m,n , l l, mk . C < 1 . E D m,k , 3 l0 = C log k n. A.


438

. .

A. , 0 A Km,n,k E A, 1 (n), (n) 0, n . nC
m

1 , A Km,n,k l(A) C log k n. [3] , A K m,n,k lu (A) 5 log k n [4] , m 3, k 2 n , m = 2, p 2 n , p , 2. E D m,k - W (E ) . = (a 1 , e1 , a2 , e2 , . . . , ar , er ) , ej . E , ai r () = (v (), w()), v () , , ai w() , , e j . W (E ) = {r ()| E }. . 2. E A, q1 , q2 A (v , w) V (E ), (q1 , v ) = w (q2 , v ) = w (q1 , v ) = (q2 , v ). A. , K m,n,k . , A, E , 1 C (n), (n) 0, mn A. 0 Km,n,k . , -




439

Km,n,k , . Q. q0 Q. a0 , E v0 . q1 (q0 , a0 ) = q1 , Q . b 1 (q0 , a0 ), . E k - , e 0 , e, b1 . v1 E , e. , q 1 = q0 . a 1 , v1 q 2 (q1 , a1 ) = q2 . q2 . b 2 (q1 , a1 ) = b2 . , q1 = q0 , : 1) a1 = a0 , 2) a1 = a0 . , , q0 = q1 . q2 = q0 . , v i E . 0 . q = qi . a0 a1 . . . ai-1 . b1 , b2 , . . . , bi . , l0 = C logk n. l() = l1 . Q = Q \ {qj |0 j i}. Q Sj 1 j r k0 , k0 r , . , k 0 r |Q |.


440

. .

Sj : Sj = {qj,t |1 t k }. S1 q1,1 . 0 . 1 1 q 1,1 (q1,1 , a0 ) = q1,1 . b 1 (q1,1 ) = b. 1 a q1,1 0 1 a1 . , q1,1 = q1,1 a0 = a1 . 2 q1,1 = q1,1 i . q1,2 . , S 1 S2 . 0 . 0 . , , = a0 , a1 . . (q , ) = (q0 , q1 , . . 2, q A = (A, Q, B , , ) . aw , . qw+1 ), q0 = q , q1 = (q0 , a0 ), . . . , qw+1 = (qw , aw ).

Y j1 ,j2 ,jd , jv = jv , v = v , 1 jv r , d r . Yj1 ,j2 ,...,jd , 0 : 1) v 1 v d (qjv ,m1 , ) (qjv ,m2 , ) m1 m2 ; 2) z = jv v , 1 v d, m1 , m2 (qz ,m1 , ) (qz ,m2 , ) m1 m2 , , (q z ,m , ) (qz ,m , ) z = z ; v1 d, v2 , 3) v1 , 1 1 v2 d, (qjv1 ,m1 , ) (qjv2 ,m2 , ) m1 m2 . d , Yj1 ,j2 ,...,jd jv = jv , v = v , 1 jv r , r ,




441

0 , , (j1 , . . . jd ) , . Yj1 ,j2 ,...,jd Pj1 ,j2 ,...,jd . . 3. P (j1 , . . . , jd ).
j1 ,j2 ,...,j
d 2 (k0 r l0 ) nr -d r -d



. j Er \ {j1 , j2 , . . . jd } Yjj ,j2 ,...jd 1 , , 0 , (j1 , j2 , . . . jd ) 1)-3), z = j 2). , Yjj ,j2 ,...jd j , , 1 P Pj1 ,j2 ,...jd =
j j1 ,j2 ,...j
d

j Er \{j1 ,j2 ,...jd }

Yjj 1 Pjj1 ,j2 ,...jd . Pjj1 ,j

,j2 ,...j
2

,...j

d

, .
d

Yjj ,j2 ,...jd s, s E k , 1 0 qj,s l qj,s l l1 0 . , l qj,s 0 , knr s Er , l El1 . P
j j1 ,j2 ,...j
d 2 k0 l 0 r n

, P
j Er \{j1 ,j2 ,...jd } j j1 ,j2 ,...j 2 (k0 r l1 ) nr-d r -d 2 (k0 r l0 ) nr-d r -d

P

j1 ,j2 ,...j

d

=

d

.

. p j1 ,...jd , 0 , E Yj1 ,...,jd . S jv mu1 , mu2 , . . . mut , (qjv ,muw , ) = w1 w t. Sjv . , , 0


442

. .

E Y j1 ,...,jd , h Sjv (q jv ,h , ) = q . pjv ,...,jd . , j1 v , p j1 ,...jd pjt ,...,jd . jq
1td

p . , d , Y j1 ,...,jd Sjt = , , Yj1 ,...,jd Sjt h Sjt (qjt ,h ) = q . p 1 , , (qjv ,h , ) = q , q jv ,h l 0 , qj1 +1 q . v ,h , , |Sjt | = ht , p1 1 p1 n1 t h n . . (qjt ,m , ) , , , (qjt ,m , ) = m 1 m k0 p 0 = k10 , l , Sjt e2 k0 . k 0 2 k 0 p0 e2 k0 2 k 0 p0 ,
jt j1 ,...,j 2 n

jt j1 ,...,j

1 . n

(1)
2d k
d

(1),

0 p . pj1 ,...,jt pj1 ,...,jt . nd d , , P 0 , E ,

P=
1 j1 d

P
r

j1 ,,j2 ,...,j

d

p

j1 ,j2 ,...,j

d

.




443

, 3 , (1) , k 2r (4C r logk n)r P 4r 0 . nr k 0 , r nr 2 (C k0 r logk n)
r

m

k

l0

log2 n.

(2)

, , k0 r , (1) (2), A, 2. , 1 r = nC , k0 = n 3 . 2 . . . . . .


[1] . ., . ., . C. . .: , 1985. [2] Hibbard T. H. Least upp er b ounds on minimal terminal state exp eriments for two classes of sequential machines // J. Asso c. Comp. Mach. 8, 4 (1961). 601-612. [ . ( ). . 2 (1966). 7-23.] [3] . . // . 184. 1 (1969). 28-29. [4] . . // . . 6 (1966). 35-50.