Конспект установочных лекций по комплексному курсу Информатика, Теория информации

Предикаты над процессами


Наряду с сетями и термами агентов множества процессов могут быть охарактеризованы через задание свойств с помощью выражений логики предикатов. Мы будем обсуждать лишь очень простые предикаты. Пусть задан процесс р = (Е0, ?0, ?),  с помощью терма #(а, р) обозначим число событий в р, помеченных действием а. Точно #(а, р) определяется следующей формулой:

#(а,р) = | {е c Ео: ? (е) = а}|.

Для бесконечных процессов значение #(а, р) может быть бесконечным. С помощью этой формулы можно образовывать предикаты и тем самым описывать множества процессов.

Пример (множества процессов через предикаты). Рассмотрим следующее множество А действий:

А = {а, b, с, d}.

Множество конечных процессов p = (Е0, ?0, ?),  можно охарактеризовать через предикат Q(p). Пусть Q(p) задан с помощью следующих формул:

(1)   0 ? # (а, р) - #(с, р) ? 1 ^

(2)   0 ? #(b, р) - #(d, р) ? 1 ^

(3)  

 е, е' c Eo: ? (е) - с ^ ? (е') = d => (е ?0 е' v е' ?0 е).

Процесс р выполняет предикат Q,

если:

(1)               число событий, помеченных через а, либо на единицу больше числа событий, помеченных через с, либо равно ему;

(2)               число событий, помеченных через  b либо на единицу больше числа событий, помеченных через d, либо равно ему;

(3)               события, помеченные через c и d не протекают параллельно.



Содержание раздела