Параллельные схемы программ Карпа-Миллера.

S = < S_I, S_C >, где S_I – информационный базис; S_C – управляющий автомат.

S_I = <M, F>

M = {x, y, z, ...} – конечное множество неких абстрактных символов, которые на этом уровне интерпретируются как некоторые переменные или ячейки.

F = {b, c, d, ...} - конечное множество неких абстрактных символов, их мы ассоциируем с неким множеством операторов.

Определить информационный базис значит задать эти два множества и еще ряд дополнительных множеств и функций:

1) символы запуска соответствующего оператора на выполнение:
= { , , ....} // |F| = | |

2) Для каждого оператора b Î F существует (определено) множество Σ_b:
b Î F [Σ_b = { b_j1, b_j2, ..., b_jk } ]
//Любой оператор b Î F [|Σ_b | > 1] называется распознавателем.
Тогда для всего информационного базиса: Σ = , где Σ – множество символов завершения операторов.

I: F → M b Î F [ in(b) M ]

O: F → M b Î F [ out(b) M ]

in( ) и out( ) – входная и выходная функции оператора. Обе они в частном случае могут быть пустыми (например, у оператора вывода).

Выч. процессом Х над инф. базисом S_I = < M, F > называется кортеж <x₁, ..., x_n>. В качестве домена выступает È S.

" x_i Î X [ x_i Î Å x_i Î S ].

Должны выполняться след. условия:

// _iX – это префикс кортежа Х до i-го элемента включительно

1. " x_i Î X $x_k Î _iX [ x_i = b_j => x_k = ] – не может быть выч. процесса, в котором есть символы завершения, но нет символов запуска.

2. " i " b Î F [ #( , _iX) ³ #(b_j, _iX) ] – символов запуска в любом префиксе должно быть не меньше, чем символов завершения.

" кортеж над доменом È S, для которого выполняются эти 2 аксиомы, называется выч. процессом над инф. базисом S_I = < M, F >.

Неформально:

Схемы программ Карпа-Миллера называются параллельными, т.к. из вышесказанного следует, что какая-то операция может начаться до того, как завершилась предыдущая (когда в кортеже символ запуска второй операции идёт до символа завершения первой), а отсюда мы получаем параллельное (думаю, слово «одновременное» произносить не стоит ;)) выполнение операций.