СЕТИ АБСТРАКТНЫХ МАШИН ВЫСШИХ ПОРЯДКОВ В ПРОЕКТИРОВАНИИ СИСТЕМ И СЕТЕЙ ХРАНЕНИЯ И ОБРАБОТКИ ДАННЫХ (БАЗОВЫЙ ФОРМАЛИЗМ И ЕГО РАСШИРЕНИЯ)

  • Published on
    06-Apr-2017

  • View
    217

  • Download
    2

Embed Size (px)

Transcript

  • 3, 2007 .

    13

    681.324 . .

    ( )

    , . , - - .

    , - , -. . , , - , . - , - , - - - -. - , - . , - , .. . , - .

    , - . -, , - -. -

  • .

    14

    , [13] [4, 5]. - - ( [69]) [10], - - [11, 12], - - .

    (), - (), :

    1 C Ob C Ob 0 F P, ..., , , , , , , , , , , , , , , , ,n aN A A F F P P I t I t F P J U U M Top Cop Lop B update test block B MB L, , , , , B, , , , , , , , , , ,L C Q W (1)

    1, ..., nA A (), , ( , , - I(t) -) ( ) ;

    1{ , ..., }nA A A ;

    C Ob C ObF F P P F P U U U U - C Ob C Ob,F F F P P P U U ;

    CF ;

    ObF ;

    CP ;

    ObP ;

    I(t), t t0 , ;

    I(t0), t0 0 , ;

    F P U ( - F P );

    J F - P ;

    : 1, 2, ...,a an U , an = const; ;

    FU ,

    ;

    PU , -

    ;

    F PU U U U ; M , -

    () I(t) ;

  • 3, 2007 .

    15

    -, ;

    Top Top : ,M M M - M;

    Cop Cop : L M M M

    Cop : L M M ( ), ;

    L ;

    Lop Lop : L L L

    Lop : L L , L; () -

    ; B ;

    B , ;

    update : ( )M P \ , - , , P ;

    test : ( )M P \ , , ;

    block : ( )M P \ , - , ,

    block update testm M m m m U ( , , );

    F P:B B U U UP \ , - ;

    MB : ( )M B P \ , ;

    L : ( )M L P \ , ;

    , - . :

    inter update testC , ,i j i jm m p m m ,

    update testinter update test

    update test

    true, ,,

    false, .

    i ji j

    i j

    m mp m m

    m m

    I

    I

    N :

  • .

    16

    Q q: M {true, false}, M; - L - ;

    W w: M {true, false}, N: - ; - W.

    . - S-, - S = F P F P.

    -

    1 2: ...i i in jf A A A A

    1 2: ... true, falsei i inp A A A () :

    af q q ; f f , p p f -

    p ( -

    n- 1 2, , ..., ,ni i i j , n - 1 2, , ..., ni i i , 1 2, , ..., ,ni i i j () );

    i p i - n - p ;

    fp f , n - f 1n - p .

    , , .

    , - , . ,L F P , - 1 2, , ..., , ...nx x x F , - P , , , . - [610] .

    ! , !! , , !!x X p x x X p x x X p x x X p x % %% % (2)

  • 3, 2007 .

    17

    - (.. - - -). n - ( 1)n . , - :

    ! , , , !! , , ,

    , , , !! , , .

    x X y Y q x y x X y Y q x y

    x X y Y q x y x X y Y q x y

    % %

    % %

    (3)

    (2). !% x , - p .

    !!% x , - p . % x p . !!% x p , -. - .

    , (3), . - ! , ,x X y Y q x y % !! , ,x X y Y q x y % ,

    ,x X % y Y ,q x y !! , ,x X y Y q x y % . - . - n - .

    (2), , x n - , . i - - x

    ipr x , 1, 2, ...,i n . . [4, 5]

    . -

    1 2 1

    1 2 1

    , , ..., ,

    , , ...,k k

    k k

    t t t t

    s t t t t

    , (4)

    1 2, , ..., kt t t , , (2); s .

    s , 1kt

    , s , 1kt .

  • .

    18

    . , - , - , ( ). - . - .

    , - , - !% , !!% , % , !!% , .. - - . ,

    ER , .. . - , - .

    :

    1 2 1

    1 2

    : ... ,

    : ... true, false ,k k

    r

    i i i i i

    j j j j

    D D D D

    D D D

    qD

    qA A qAP , 1, 2, ...,q n . - .

    FU PU -

    (4), qA A , 1, 2, ...,q n .

    - , . , , , , .

    - , . -. .

  • 3, 2007 .

    19

    1. I . - ; - | ( );

    Top , .. ( (-) ); Cop - - - 1 :Op L M M M .

    2. II . I , .

    3. III II , - 3 : |, , b . : ,, ; : .

    - , - . .

    4. IV , Top -. . ,

    B Top Cop , .. - . Cop , -, - - : 2 :Op L M M. IV ().

    , - , - - (). . , , - , , . - . .

    , ; , , - , , .

  • .

    20

    .

    1. n -, , - , n - , .

    2. n -, n - .

    3. (), - .

    4. n - , - n - .

    5. n -, n-, A n , A ( ).

    6. ()-, - ()- (, - ) - , - .

    7. , - Top Cop B ( Top ,

    Cop

    B ). 8. ,

    - Top , Cop B .

    . 16 , - 18 .

    , . - - , . , - . , - ( )p P A p , , ( )r P A r , . - .. [10].

    - , -

  • 3, 2007 .

    21

    . , ( )

    ( ! ) ( ) ( ! ) ( ) ( ! ) ( , )

    {... ( , ) false ...} E E E

    m x X p x y Y q y s s x y

    s x y R R R

    % % %

    (5)

    c ix x -

    p , -

    jy y . -

    (5) s ,

    ,i js x y , ( -) ix jy . (5)

    , .. - ( -) . (5) - , (5) - :

    ( ! ) ( ) & ( ! ) ( ) ( ! ) ( , )

    {... ( , ) false ...} .E E

    m x X p x y Y q y s s x y

    s x y R R

    % % %

    (6)

    (6) _ , - . - x y _ .

    1. , , - , - - .

    2. - , .

    3. , - , - . - - .

  • .

    22

    1. Gurevich, Y. On Kolmogorov machines and related issues. The logic in computers science column / Y. Gurevich // Bulletin of Europian Assoc. for Theor. Comp. Science. 1998. 35. . 7182.

    2. Dexter, S . Gurevich abstract state machines and Shnhage storage modification ma-chines / S. Dexter, P. Doyle, Y. Gurevich // Journal of Universal Comp. Science. 1997. V. 3. 4. . 279303.

    3. , . . / . . // . . . . . - . 1979. 88. . 1518.

    4. Gurevich, Y. Evolving Algebras 1993: Lipari Guide, Specification and Validation Methods, ed. E. Brger / Y. Gurevich // Oxford University Press. 1995. P. 936.

    5. Gurevich, Y. Draft of the ASM Guide / Y. Gurevich // University of Michigan EECS Department Technical Report CSE-TR-336-97. 1997. May. P. 127.

    6. , . . , / . . . . : , 1991. 448 .

    7. , . . / . . // - : 3- . . 2. : / . . . . . : , 1990. . 1428.

    8. , . . / . . , . . . . : , 1979. 320 .

    9. , . . / . . , . . , . . - [ .]. . : , 1991. 480 .

    10. , . . / . . // - : 4- . . : , 2000. 2 .

    11. , . . . . / . . , . . , . . . : , 1978. 320 .

    12. , . . / . . , . . , . . . : , 1980. 252 .

Recommended

View more >