Введение. Задачи построения планов по прецедентам достаточно хорошо известны.
    Такого рода задачи возникают в тех сферах деятельности, где возникает потребность в построении модели каких-либо процессов на основе экспериментальных или ретроспективных данных, например, при синтезе поведения сложных технических систем по прецедентной информации или при синтезе моделей бизнес - процессов по множествам примеров.
    Хорошей иллюстрацией такой сферы деятельности является клиническая медицина; в качестве примера можно привести задачу восстановления описаний лечебно-диагностических процессов на основе записей в электронных историях болезни; в связи с этим мы будем достаточно часто апеллировать к иллюстрациям и примерам из этой сферы.
    Во всех задачах такого рода одним из центральных понятий является понятие потока работ.
    Вторым важным понятием является понятие процесса над множеством дискретных событий.
    Если отвлечься от деталей используемых формализмов, то, по существу, поток работ над множеством дискретных событий есть упорядоченное множество операторов, действующих на множестве всех подмножеств множества дискретных событий.
    Процессом над множеством дискретных событий назовем модифицированный поток работ, включающий кроме множества операторов связанные с каждым оператором подмножество множества дискретных событий и условия применимости оператора.
    В [1] были введены последовательные и параллельные потоки работ, однако не было рассмотрено устройство операторов, образующих потоки и условия возникновения тех или иных потоков.
    Здесь будут рассмотрены три новых типа потоков: конкурентные, условные и итеративные, методы их извлечения из множеств примеров, их свойства, процессы над множествами дискретных событий и те различия в подмножествах множеств дискретных событий, условиях применимости и свойствах операторов, которые порождают различные типы процессов.

1.Маршруты в потоках работ

1.1. Потоки работ как допустимые последовательности операторов

    Начнем с описания понятие "состояние"; например, состояние лечебно-диагностического процесса.
    Состояние включает множество значений наблюдаемых, исследованных и измеренных признаков, множество значений вычисленных признаков и множество значений признаков, заболеваний и патологических процессов, сведения о которых получены на основании рассуждений.
    Обозначим множество заболеваний и патологических процессов через U, а множество значений признаков, наблюдаемых, исследованных и измеренных в некоторый момент или интервал времени через P.
    С формальной точки зрения, элементы U можно считать замкнутыми формулами логического (или какого-либо иного формального языка) языка первого порядка, элементы второго множества - одноместными атомарными формулами логического языка первого порядка.
    Таким образом, заданы:
-некоторое непустое множество U фактов или замкнутых формул логического языка первого порядка;
-множество P свойств или одноместных атомарных формул языка первого порядка.
    Эти множества можно пополнить с помощью специальных процедур замыкания, основанных на рассуждениях и вычислениях [2].
    Задано также множество операторов, представляющих активные части лечебных мероприятий, т.е. действия, которые входят в те или иные лечебные мероприятия и изменяющие в результате состояние пациента [2]. Т.е. задано множество операторов O, действующих: из 2U в 2U и из P в P, так что о S(n) = S(n+1),
    где О -множество операторов, о О O, 2U - множество всех подмножеств множества U, S(i) - i-е состояние, S(i)О 2U.
    Каждому оператору поставлено в соответствие условие его применимости, т.е. задано отображение CON: O ® 2U, так что CON(o) = con, где o ОO, con О 2U .
    Рассмотрим следующую ситуацию: в лечебном учреждении имеется информационная система, в базе данных которой ведутся записи о назначениях и исполнении лечебных мероприятиях по некоторому числу случаев и различным нозологическим формам. Каждый случай, т.е. записи обо всех лечебных мероприятиях, назначенных конкретному пациенту, будем называть примером или экземпляром.
    К примерам предъявляются следующие требования: для каждого мероприятия должно быть указано его наименование и время исполнения.
    Рассмотрим возможные последовательности применения тех или иных лечебных мероприятий
    Итак W(O) -семейство последовательностей вида
        w = (oi ,oj , …,ok ) над множеством O операторов.
Здесь i, j, … , k - элементы N множества натуральных чисел и i < j < … < k .
    Можно считать, что с каждой последовательностью w связаны некоторые отображения ordw и labw ;
    ord : N> 2U , так что ord (n) = s (n), где s (n) О 2U
    labw: N > O , так что lab (n) = on где on Оw. Первое отображение упорядочивает состояния пациента, второе - упорядочивает применяемые операторы.
    На множестве W(O) задано некоторое отношение r, порождающее фактор - множество Wr множества W(O). С содержательной точки зрения это отношение разбивает множество всех примеров на классы эквивалентности по нозологическим формам; т.е., в каждом классе содержатся примеры по одной и тоже нозологической форме (разумеется, относящиеся к различным пациентам).
    Ближайшей целью является поиск полного описания каждого из классов эквивалентности по отношению r, т.е. таких описаний, что каждый элемент из W(O) удовлетворял бы одному из классов.
    Иначе говоря, задача состоит в том, чтобы опираясь на множества примеров, входящих в классы эквивалентности по прямому разбиению r, построить описания G({w}) каждого из классов эквивалентности {w} из Wr, такие, что каждый пример w, входящий в некоторый класс эквивалентности {w} удовлетворял бы описанию G({w}) этого класса. Точный смысл этих понятий будет введен несколько позже, пока же можно сказать, что понятие описание класса эквивалентности соответствует некоторому описанию множества всех примеров класса.
    Далее мы покажем, что построенные описания являются полными, т.е. всякий новый пример, не принадлежащий W(O), но сохраняющий разбиение r, (т.е. пополняющий один из существующих классов эквивалентности {w}О Wr, удовлетворяет описанию G({w}) этого класса эквивалентности.
    Иначе говоря, если w О W(O), w1 П W(O) и отношение r на W(O) И {w1} порождает то же фактор - множество, что и на W(O), то найдется класс эквивалентности {w}rОWr, такой что w1 |= G({w}).
    Другими словами, задача состоит в том, чтобы построить описания каждого из классов эквивалентности, такие, что каждый новый пример, даже не использованный при построении описания, но оказавшийся в какой - то момент в системе, удовлетворял бы описанию одного из классов. Это свойство классов и означает полноту описания каждого из них.
    Заметим, что эту задачу можно трактовать как задачу распознавания образов в её алгебраической постановке [3].
    Затем мы рассмотрим условия появления различных типов примеров в классах. Эти различия, как будет показано, порождены различиями в состояниях пациентов и свойствах операторов и их композиций, которые и обуславливают допустимость различных последовательностей исполнения операторов.
    Это позволит построить схемы порождения примеров конкретных процессов на основе описаний классов, свойств операторов и некоторой дополнительной информации, входящей в описания состояний.
    Точнее говоря, построенные общие описания классов лечебно-диагностических процессов могут быть использованы для построения экземпляров лечебно-диагностических процессов, учитывающих условия конкретной клиники и, в случае наличия таковых, ограничения, вызванные особенностями пациента.

1.2. Маршруты в потоках работ
    Анализ примеров показывает, что какую бы нозологическую форму мы бы ни взяли, существуют различные примеры (последовательности операторов), реализующие её лечение.
    Эти примеры отличаются различным порядком выполнения наборов лечебных мероприятий, наличием отличающихся друг от друга фрагментов, т.е. некоторых подпоследовательностей и некоторой кратностью повторения определенных подпоследовательностей. Для описания различных типов последовательностей такого рода используется понятие маршрута в потоке работ.
    Маршрут в потоке работ в нашем случае есть общее описание некоторого подмножества примеров, имеющих одинаковый порядок исполнения лечебных мероприятий по отношению к некоторому опорному примеру.
    В [2] выделяется четыре вида маршрутов: последовательные, параллельные, условные и итеративные.
    Последовательный маршрут соответствует временному отношению строгого линейного порядка на множестве операторов. Это означает, что оператор oj может быть выполнен только после того, как будет выполнен оператор oi.
    Иначе говоря, существует некоторая подпоследовательность операторов, которая в каждом из примеров выполняется в одном и том же порядке. Эта подпоследовательность и формирует последовательный маршрут в описании множества примеров.
    Параллельный маршрут означает, что порядок выполнения операторов oj и oi не имеет значения. Таким образом, параллельный маршрут соответствует существованию в множестве примеров такого подмножества, в котором некоторая пара операторов имеет инверсный порядок по отношению к опорному примеру.
    Условный маршрут соответствует выбору между двумя или более возможными продолжениями процесса. Это означает, что существуют такие примеры, в которых некоторый подпоследовательность операторов по составу операторов отличается от соответствующей (в некотором смысле, который будет уточнен ниже) подпоследовательности в опорном примере.
    Итеративный маршрут соответствует повторению некоторого подпроцесса, пока не будут выполнены определенные критерии.
    Здесь введем еще один тип маршрута, который назовем конкурентным.
    Конкурентный маршрут возникает тогда, когда существует тройка операторов, порядок выполнения которых в некотором подмножестве примеров обладает зеркальной симметрией по отношению к опорному примеру. Этот маршрут напоминает параллельный, однако, отличие состоит в том, что переставляемые операторы (лечебные мероприятия) не соседствуют - между ними находится некоторый "неподвижный" оператор.
    Уточним теперь определения маршрутов. Для этого введем понятие частичного прецедента.
    Определение 1. Частичным прецедентом для примера w = (…, oi , oj , p , ok on, …), (где p - некоторая последовательность операторов из О), будем называть всякий пример wp , такой, что последовательность (oj , pp , ok ) Н wp , (где p p - некоторая последовательность операторов из О).
    Графически это выглядит следующим образом:

w: … ® oi ® oj ® p ® ok ® on® … w p: … ® oi ® oj ® p p ® ok ® on® …

    В качестве такого примера w можно выбрать, вообще говоря, любой пример класса, т.к. приведенные ниже определения "симметричны" относительно примеров, в них участвующих. Выбранный пример будем называть опорным.

    Определение 2. Будем говорить, что опорный пример, а также все примеры, совпадающие с ним, порождают последовательный маршрут.
    Граф маршрута:

… ® oi ® oj ® ok ® oq® …

    Определение 3. Если среди множества примеров некоторого класса эквивалентности {w}r найдутся w1, w2, …,wn - частичные прецеденты для для опорного примера w = (…, oi , oj , p , ok on, …), из того же класса, такие что если p = (on , om ), то p1 = … = p n = (om , on), будем говорить, что примеры w, w1, w2, …,wn порождают параллельный маршрут.
    Граф маршрута:

Определение 4. Если среди множества примеров некоторого класса эквивалентности {w}r найдутся w1, w2, …,wn - частичные прецеденты для опорного примера w из того же класса, такие что если p = (on , om , op ) (p Н w ), то p1 =…= p n = (op , om , on) (p1 Н w1, …, p n Н wn ), будем говорить, что примеры w, w1, w2, …,wn порождают конкурентный маршрут.
    Граф маршрута:

Определение 5. Если среди множества примеров некоторого класса эквивалентности {w}r найдутся w1, w2, …,wn - частичные прецеденты для опорного примера w из того же класса, такие что p1 = … = p n - некоторая последовательность операторов, не совпадающих с операторами из p (p Н w; p1 Н w1, …, p n Н wn ) и если примеры w1, w2, …,wn не порождают параллельного или конкурентного маршрута, то будем говорить, что они порождают условный маршрут.
    Граф маршрута:

    Определение 6. Если среди множества примеров некоторого класса эквивалентности {w}r найдутся w1, w2, …,wn - такие что p1 = … = p n = (p1 Н w1, …, p n Н wn ), то будем говорить, что примеры w1, w2, wn порождают итеративный маршрут (число j+k будем называть длиной маршрута).

    Замечание 1. В определениях 3-5 вовсе необязателен выбор одного и того же примера в качестве опорного. Действительно, если w и w1 - различные опорные примеры, то они также породят некоторый маршрут. Поскольку далее будет показано, что описанными типами маршрутов исчерпываются все маршруты в графе описания класса эквивалентности, то в качестве опорного примера можно выбрать любой из примеров w или w1 .
    Теперь перейдем к уточнению понятия описание класса эквивалентности. Поскольку в соответствии с предъявляемыми к классам эквивалентности требованиями, каждый элемент W(O) должен удовлетворять описанию одного из классов, то описание каждого класса должно содержать все маршруты, порожденные содержащимися в классе примерами.
    Таким образом, описание G({w}) каждого класса эквивалентности {w}О Wr уместно считать графом, содержащим в качестве подграфов маршруты, порожденные всеми примерами w О{ w}.

Рис. 1. Пример описания класса эквивалентности. (Здесь вершины графа обозначены целыми числами)

    1. Построение описаний классов эквивалентности

     Ближайшая наша задача состоит в том, чтобы для каждого из классов эквивалентности {w} из Wr построить его описание G({w}) в виде графа, пример которого приведен на рис.1. При этом построенному описанию должны удовлетворять все элементы класса {w}.
     Понятно теперь, что это последнее обстоятельство означает, что для каждого примера w из класса {w} в графе G({w}) должен найтись эквивалентный ему подграф.
    Замечание 2. Будем считать, что примеры, содержащиеся в классах эквивалентности, удовлетворяют принципу частичной прецедентности. Это означает, что мы "закрепляем концы" примеров.
     Действительно, с содержательной точки зрения, трудно представить пример, в котором переставлены первый оператор с последним. Немного найдется клиник, где лечение больного начинается с его выписки из клиники, а завершение лечения - с регистрации в регистратуре.

     Перейдем далее к представлению графов посредством их матриц инцидентности. На множестве матриц инцидентности введем ассоциативную и коммутативную операцию покомпонентного сложения, сохраняющую единицу:

    если А =[aij ] и В = [bij ]- матрицы инцидентности, то А+В = [aij ] + [bij ],
    где [aij ] + [bij ] = max ([aij ], [bij ]).

    Например, для последовательности

o1 ,o2 , …,ok

    такая матрица будет иметь вид:

    a12 = a23 = … = ak-1,k = 1; все остальные её элементы равны нулю.
     Тогда для класса эквивалентности, содержащего лишь последовательности вида
    … ® oi ® oj ® p ® ok ® oq® , т.е. множество примеров, порождающих последовательный маршрут (см. Определение 2), матрица инцидентности (с точностью до перестановок строк и столбцов) будет иметь такой же вид:
    a12 = a23 = … = ak-1,k = 1 ; все остальные её элементы равны нулю.

    Определение 7. Описанием G({w}) каждого класса эквивалентности {w} будем называть такую матрицу M({w}), для которой матрица инцидентности каждого из графов маршрутов, порожденных примерами класса {w} является субматрицей.
    (Матрицу А =[aij ] будем называть субматрицей матрицы В = [bij ], если для каждого aij найдется bij, такой, что aij= bij ).
    Пусть {M} - множество матриц инцидентности всех примеров класса {w} и только их. Через М(wj) обозначим матрицу инцидентности графа примера wj (в дальнейшем фразу матрица инцидентности графа примера wj будем заменять фразой матрица примера wj).
Теорема 1., где суммирование в указанном выше смысле выполняется по всем примерам wj из класса {w}.

        Эта теорема, по - существу, обосновывает корректность процедуры построения описания класса.

    Пусть M(w) - матрица описания некоторого класса эквивалентности {w}. Покажем, что какой бы мы ни взяли пример из класса, он порождает хотя бы один из маршрутов, определенных выше.
    Теорема 2. Для любого w, если w О{w}, w |= M(w). Иными словами, для всякого примера из класса {w}, порождаемый им маршрут есть один из маршрутов, входящих в описание класса. Эту теорему можно считать теоремой о полноте описания класса.
    Следствие. Всякий новый пример, не принадлежащий W(O), но сохраняющий разбиение r, (т.е. пополняющий один из классов эквивалентности{w}О Wr), удовлетворяет описанию одного из классов эквивалентности.

3.Процессы и маршруты в них

    В предыдущем разделе мы рассмотрели различия в потоках работ, порождающие различные типы маршрутов. Однако существуют веские основания считать, что причинами возникновения тех или иных маршрутов являются некоторые более глубокие свойства процессов, отражающие их содержательные особенности.
    Для уточнения понятия процесса и указанных соображений следует рассмотреть вначале вид операторов и преобразования ими выполняемые.
    Напомним, что операторы из О действуют из 2U в 2U и из P в P, где U - некоторое непустое множество фактов (например, множество замкнутых атомарных формул логического языка первого порядка), а P -множество свойств (в частности, ими могут быть одноместные атомарные формулы языка первого порядка).
    Среди таких свойств могут быть свойства количественного характера, которые мы обозначим через P1, и качественного, которые обозначим через P2.
    Каждый оператор o имеет вид:

        где Ф - семейство функций времени { f 1 ,f 2 ,…, f n} из F, действующих из декартовых степеней множества P1 в P1 [5];
    P2 - множество значений неколичественных признаков, появляющихся в результате действия оператора о;
    Z- множество новых фактов, появляющихся в результате действия оператора о;
    Механизм действия оператора о таков:
    о: а) 2U ® 2U так, что оs(n) = s(n+1), где s (n) О 2U
         s(n+1) = s(n) И Z либо s(n+1) = Z, где Z- множество новых фактов, появляющихся в результате действия оператора о;
         P2 ® P2 так, что о P2 (n) = P2 (n) И P2 (n +1) либо oP2 (n) = P2 (n +1), где P2 (n +1) - множество значений неколичественных признаков, появляющихся в результате действия оператора о;
    б) (P1)k ® P1 так, что fa (p1(n), p2(n), …, pk(n)) = pa(n +1) fb (p1(n), p2(n), …, pk(n)) = pb(n +1) fc (p1(n), p2(n), …, pk(n)) = pc (n +1) ,
    где fa, fb, …, fc О Ф.

    Замечание 3. Два различных механизма действия оператора о описанных в п. а): X:= X И Y и X:= Y соответствуют двум различным операторам присваивания - операторам, добавляющим новые элементы в множество (консервативный случай) и операторам, заменяющим элементы множества (неконсервативный случай).
    С содержательной точки зрения, речь идет либо о появлении в новом состоянии новых признаков при сохранении имеющихся, либо об исчезновении в новом состоянии старых признаков и появлении новых. Оба случая имеют место в различных приложениях.
    Таким образом, если s (n) И P1(n) И P2 (n)
    (где P1(n) = p1(n) И p2(n) И …, pk(n)), назвать состоянием S(n) процесса S(n), то o S(n) = S(n+1), т.е., операторы из семейства О играют роль операторов переходов.

    В первом разделе было введено отображение CON: O ® 2U, так что CON(o) = con, (где o ОO), con О 2U , ставящее в соответствие каждому оператору некоторое подмножество множества U, т.е. множества фактов. Это подмножество con будем называть условием оператора о и обозначать через c либо c(о)

    Определение 8. Оператор о будем называть применимым к состоянию S (n), если c(о) Н S(n).
    Определение 9. Последовательность π = ((ci, oi), (cj,oj), …,(ck,ok) ) будем называть процессом, если для каждых двух её элементов (сn, on) , (сn+1, on+1) оператор on+1 применим к состоянию S(n).
    Множество всех примеров процессов обозначим через P(О). Если q - отображение из W(O) в P(О), так что q(

) = ((ci, oi), (cj,oj), …,(ck,ok) ), то легко видеть, что q - изоморфизм относительно упорядочения, а W(O) и P(О) - изоморфно упорядоченные множества. Отсюда следует, что определения 1-7 и теоремы 1 и 2 очевидным образом переносятся на множества примеров процессов.
    Выясним теперь свойства операторов и некоторых операций над ними, приводящие к различным типам примеров процессов и, следовательно, к различным маршрутам, порождаемым их множествами.
    Наиболее простыми оказались причины возникновения условных и итеративных маршрутов.
    Появление условных маршрутов связано с тем, что возможны близкие в некотором смысле состояния процессов, к которым применимы различные операторы с близкими условиями. Если на к-м шаге некоторого процесса формируется состояние S!(k), отличающееся от состояния S(k), то вместо оператора о становится применимым оператор о!, условие которого выполнимо в состоянии S!(k).
    Появление итеративных маршрутов связано с наличием в примерах процессов некоторого критерия (условия), выполнение которого позволяет осуществить переход к следующему оператору.
    Для выяснения причин порождения иных типов маршрутов введем операцию суперпозиции операторов и рассмотрим некоторые её свойства.

    Определение 10. Суперпозицией о1 о2 операторов о1 и о2 называется