46727 (Автоматно-графовая формальная модель композитного документооборота)

УДК 681.3

М.Ю. КРУКОВСКИЙ

АВТОМАТНО–ГРАФОВАЯ ФОРМАЛЬНАЯ МОДЕЛЬ КОМПОЗИТНОГО ДОКУМЕНТООБОРОТА.

Abstract: This paper describes approach of usage finite states machine for creating a system of of FSMs that are connected by graphs. Document management system implemented as a SM that operates with FSMs as a behavior models. In the paper covered issues of document management implementation based on hierarchical finite state machine.

Key words: electronic document management, composite docflow, workflow, formal model, automat model, graph model, hierarchical finite state machine.

Анотація: У статті розглянуто застосування скінчених автоматів для створення системи автоматів, зв’язаної графами. Документообіг представлено у вигляді автомата, який оброблює автомати, кожен із них моделює поведінку одиниці системи документообігу. У статті розглянуто моделювання складних систем документообігу за допомогою ієрархічного скінченого автомата.

Ключові слова: електронний документообіг, композитний документообіг, процесне керування, графова модель, формальна модель документообігу, автоматна модель, графова модель, ієрархічний скінчений автомат.

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

Ключевые слова: электронный документооборот, композитный документооборот, процессное управление, формальная модель документооборота, автоматная модель, графовая модель, иерархический конечный автомат.

1.Введение

В современном обществе идет процесс интенсификации вычислительных и информационных технологий во всех отраслях деятельности [1]. Внедрение электронного документооборота является актуальной задачей современного общества. Внедрение систем электронного документооборота позволяет сделать процесс движения документов управляемым и контролируемым, что обеспечивает более качественные услуги управления.

При решении задач электронного документооборота большое значение имеет использование формальных моделей в проектировании, разработке и внедрении СЭД. Применение формальных моделей позволяет специалистам оперировать измеримыми объектами, к которым может быть применен апробированный математический аппарат.

В отечественной и зарубежной науке существуют примеры применения теории графов и теории автоматов как самостоятельных формальных моделей документооборота. Одной из первых модель документооборота с применением теории графов была предложена в работе [2]. Зарубежные ученые рассматривали применение автоматов для моделирования информационного взаимодействия рабочих групп [3]. Другими авторами автоматы были использованы для моделирования связной системы взаимодействующих процессов при решении задач процессного управления [4]. Автор статьи предложил формальные модель документооборота, построенная на графах [5] и автоматах [6].

2. Постановка задачи

Целью настоящей статьи является обобщение полученных автором в работах [5,6] результатов и создание автоматно-графовой формальной модели электронного документооборота, построенного на аппарате теории графов и теории автоматов.

Теория графов позволяет отразить связность формальной модели, наглядным образом представить установленные связи между участниками документооборота. Аппарат графов дает возможность описывать взаимодействия участников и документов с помощью матрицы инцидентности.

В свою очередь, теория автоматов позволяет реализовать логику ветвления движения документов между участниками процессов документооборота. Автомат позволяет установить реакцию элементов системы документооборота на изменения в системе. С помощью автоматов процессы документооборота могут быть представлены в виде элементов с предсказуемым поведением и описанными интерфейсами.

Таким образом, при применении теории графов и теории автоматов к формальной модели документооборота, появляется возможность представить документооборот в виде автоматов, связанных графами. Каждый автомат представляет собой поведенческую единицу системы документооборота, которая обладает своим поведением. Результаты работы автоматов поступают на вход другим поведенческим элементам системы документооборота, которые также реализованы автоматами. Связность и направленность передачи выходных результатов в качестве входных алфавитов определяется графом документооборота.

Приведенное выше описание модели представляет собой конечный автомат (КА), который в свою очередь оперирует автоматами. Входной и выходной алфавиты представляют собой КА, который реализует поведенческие единицы системы документооборота. Функция переходов задается с помощью графа, определяющего связность поведенческих единиц. Такой автомат в литературе [7] называется иерархическим конечным автоматом (Hierarchical Finite State Machine).

В следующем разделе рассмотрим описанную выше модель боле подробно.

3. Синтез автоматно–графовой формальной модели

Адаптируем описанный выше математический аппарат для создания формальной модели композитного документооборота. Для решения этой задачи представим документооборот в виде связанной последовательности процессов, протекающих в дискретном временном пространстве.

3.1. Формальная модель документооборота

Для моделирования документооборота будем использовать формальную модель композитного документооборота, предложенную автором в работе [8]. В этой модели процесс документооборота может быть представлен в виде трех конечных множеств и связей элементов этих множеств между собой. Математическая нотация представлена в виде тройки

где:

– формальная модель документооборота;

– множество участников;

– множество действий;

– множество состояний документов.

Нотация означает следующее: «Документооборот – это множество действий, производимых множеством участников над множеством состояний документов». Множество { } определяется как конечное множество ролей, которые могут быть назначены фактическим участникам документооборота. Множество { } определяется как конечное множество действий, выполнение которых допустимо в пределах рассматриваемой системы документооборота. Множество форм { } – конечное множество состояний, которые могут принимать документы после произведения над ними действий из множества { } участником из множества { }.

Таким образом, поведение участника документооборота может быть представлено в виде последовательности состояний документов. Совокупность всех состояний документов представляет конечное множество, которое полностью описывает все возможные сценарии поведения участников.

3.2. Модель связности поведенческих единиц на графах

Для построения графа модели документооборота предлагается использовать способ отображения документооборота графами, предложенный автором в работе [5]. Для задания множества вершин графа будем использовать множество возможных состояний документов . Ребра графа зададим с помощью множества действий Д. Установим это соответствие таким образом, чтобы выполнялись следующие правила:

– одной вершине графа соответствует один и только один элемент множества ;

– одному ребру графа соответствует один и только один элемент множества ;

– одному элементу множества соответствует одна и только одна вершина графа;

– одному элементу множества соответствует одно и только одно ребро графа.

Такое тождественное отображение множеств состояний в множество вершин и множества состояний в множество ребер e можно математически определить следующим образом: для любого справедливо утверждение и , где . То есть определяются две парных грамматики – первая грамматика для установления перевода Ф в v, вторая грамматика – для установления перевода Д в e.

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

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

3.3. Модель поведенческой единицы на автоматах

В предложенной автором автоматной модели документооборота [6] система представляется в виде детерминированного конечного автомата. Автомат, представляющий поведенческую единицу документооборота задается общепринятой нотацией конечного автомата. В соответствии с ней автомат представляется следующим образом:

,

где – конечное множество состояний документов, которое тождественно множеству { }, что следует из определения композитного документооборота;

– конечное множество входных символов, образующих входной алфавит и представляющих собой данные, которые поступают на вход системы документооборота;

– функция переходов, аргументами которой являются текущее состояние и входной символ, а значением – новое состояние;

– начальное состояние (или множество начальных состояний докуемнтов) из множества ;

– множество заключительных, или допускающих состояний из множества .

Множество состояний автоматов {Q} получается из множества состояний документов. Завершающие состояния выделяются из общего множества состояний путем анализа каждого из состояний. Если при анализе выявляется состояние, которое имеет одну или несколько входящих связей, но не имеет ни одной исходящей, то оно помечается как завершающее. Состояния моделирующего автомата упорядочиваются таким образом, чтобы документооборот был представлен состояниями документа в порядке от начального состояния документа к завершающему.