WWW.RU.I-DOCX.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Электронные документы
 

«Обобщенная модель системы автоматов И.Б. Бурдонов, А.С. Косачев Институт системного программирования, Москва, Россия igor kos посвящен моделированию, ...»

Обобщенная модель системы автоматов

И.Б. Бурдонов, А.С. Косачев

Институт системного программирования, Москва, Россия

igor@ispras.ru, kos@ispras.ruДоклад посвящен моделированию, композиции и детерминизму составных систем. Компонент системы моделируется конечным автоматом с несколькими входами и выходами, а взаимодействие – синхронным обменом сообщениями по симплексным каналам связи, связывающими выходы со входами и называемыми соединениями. Переход автомата предъявляет требования к соообщениям на всех входах и выходах автомата и отдельно указывает часть входов и выходов, по которым сообщения принимаются или посылаются. Синхронность означает, что требования автоматов, связанных соединением, должны быть согласованы.

Задан конечный алфавит сообщений M, M, и M = M{}. Автомат в алфавите M – это набор A=(M,I,J,S,T,s0), где I – множество входов, J – множество выходов, S – множество состояний, TSXPYQS – множество переходов, где X={x|x:IM} – множество стимулов, Y={y|y:JM} – множество реакций, P=2I – для приёма сообщений, Q=2J – для посылки сообщений, s0S – начальное состояние, и выполнены условия: 1. IJ=; 2. передаются непустые сообщения: (s,x,p,y,q,t)T px1(M) & qy-1(M); 3. автомат всюду определён по стимулам: sS xX p,y,q,t (s,x,p,y,q,t)T; 4. приём сообщений выполним независимо от посылки сообщений: (s,x,p,y,q,t)T q`y-1(M) t` (s,x,p,y,q`,t`)T; 5. множества I, J и S конечны. Для a=(s,x,p,y,q,t) обозначим sa=s, xa=x, pa=p, ya=y, qa=q, ta=t. Для A=(M,I,J,S,T,s0) обозначим IA=I, JA=J, SA=S, TA=T, s0A=s0.



Пусть V – конечное множество автоматов в алфавите M. Входы и выходы автоматов разные: A,BV (AB IAIB= & IAJB= & JAJB=), состояние автомата – множество, и состояния разных автоматов не пересекаются: A,BV sASA sBSB (AB sAsB=). Система автоматов – это набор R=(M,V,E), где E:EDom  EIm – биекция, определяющая соединения, где EDomJR, EImIR, JR={JA|AV} – множество всех выходов всех автоматов, IR={IA|AV} – множество всех входов всех автоматов. Для R=(M,V,E) обозначим: VR=V, ER=E. Вход iIR\EIm и выход jJR\EDom – внешние, связывающие систему с её окружением.

Вводится композиция в духе CCS [1], но с учётом соединений. Обозначим: для функции f и множества N: f/N = f \ {(z,f(z)) | zNDom(f)}; для отношения эквивалентности a~b = (a&b)(a&b); для множества переходов T: States(T) = {sa|aT}{ta|aT}. Пусть A,BV, (j,i)E, jJA, iIB.

Условие композиции переходов f(a,j,i,b) = aTA & bTB & (A=B a=b) & ya(j)=xb(i) & (jqa ~ ipb).

Композиция переходов a[j,i]b = (sasb, xaxb/{i}, papb\{i}, yayb/{j}, qaqb\{j}, tatb).

Композиция множеств переходов: G[j,i]H = {a[j,i]b|aG & bH & f(a,j,i,b)}.

Композиция автоматов: A[j,i]B = (M,IAIB\{i},JAJB\{j},{s0As0B}States(TA[j,i]TB),TA[j,i]TB,s0As0B).

Композиция системы: R[j,i] = (M,V\{A,B}{A[j,i]B},E\{(j,i)}).

Композиция ассоциативна. Композиция R^ системы R по последовательности всех её соединений не зависит от их порядка, не имеет соединений, и все её автоматы не связаны между собой соединениями, т.е. все их входы и выходы внешние. Для использования системы в качестве компонента другой системы, она докомпоновывается до одного автомата с помощью композиции без соединения (для несвязанных автоматов).

a[]b = (sasb,xaxb,papb,yayb,qaqb,tatb), G[]H = {a[]b|aG & bH},

A[]B = (M,IAIB,JAJB,{s0As0B}States(TA[]TB),TA[]TB, s0As0B), R[A,B] = (M, V\{A,B}{A[]B}, E).

Автомат A детерминирован, если 1. состояние s и стимул x однозначно определяют приём сообщений p и реакцию y и 2. одинаково помеченные переходы из одного состояния совпадают. Если в системе R все автоматы детерминированные, разбиты на два класса: класс «вершин» и класс «дуг», каждое соединение связывает автоматы разных классов и в каждом автомате класса «дуг» реакция зависит только от состояния (не зависит от стимула), то композиционный автомат R^ детерминирован.





Преложенную модель можно использовать для тестирования детерминированных составных систем. Если ошибки могут быть только в компонентах, а все соединения правильные, тестирование сводится к проверке правильности переходов каждого автомата. Однако автомат тестируется только как часть системы, что похоже на тестирование в контексте [2]. Предполагается, что известно, какими должны быть автоматы (с точностью до изоморфизма), и именно это проверяется. Тест наблюдает как состояния автоматов, так и передаваемые сообщения. Такие предположения оправданы, например, при имитационном тестировании аппаратуры (simulation-based verification) [16].

Литература

1. Milner R. Communication and Concurrency. Prentice-Hall, 1989.2. Revised Working Draft on “Framework: Formal Methods in Conformance Testing”. JTC1/SC21/WG1/Project 54/1, ISO Interim Meeting, ITU-T on. Paris. 1995.3. A. S. Kamkin, M. M. Chupilko. Survey of modern technologies of simulation-based verification of hardware. Programming and Computer Software, 2011, vol. 37 (3), pp. 147–152.

Похожие работы:

«Пояснительная записка. Литература — базовая учебная дисциплина, формирующая духовный облик и нравственные ориентиры молодого поколения. Ей принадлежит ведущее место в эмоциональном, интеллектуальном и эстетическом развитии школьников, в формировании их миропонимания и национального самосознания, без чего невозможно духов...»

«УДК 612.062СТРЕСС, КАК СОСТАВЛЯЮЩИЕ УЧЕБНОГО ПРОЦЕССА СТУДЕНТОВ. В.З. МовсумовСургутский государственный университет, г.СургутАннотация: Стресс, несмотря на мнение людей, является серьёзной причиной и фактором, способствующим возникновению различных заболеваний в организме человека. А его влияние студе...»

«Информация о результатах повторного аукциона по продаже земельных участков 11 января 2017 года в 14 часов 30 минут организатор повторного аукциона – комитет по земельно-имущественным отношениям администрации муниципального образования Заокский район на основании постановления администрации м...»

«Интернет рождение новой реальности Мир погрузился в глубину С.Лукьяненко Прежде всего: для чего нужны исследования влияния Интернета на психику человека? Влияние Интернета на погруженных в его "глубину...»

«Урок№4 Тема: "Семейство Розоцветные. Особенности строения цветка, плода, жизненные формы". Лабораторная работа № 23 "Строение цветка и плода растений семейства Розоцветные". Цель: Показать обусловленность структу...»

«Развлечение "День России" (Сценарий для старшей группы № 8 (СП № 2. Д/с № 39) Воспитатель Узикова О. А)Цель: Развитие патриотических чувств. Задачи. — Воспитание у детей интереса, любви к Родине, чувства гордости. — Вос...»

«R IPC/CE/49/2 оригинал: английский дата: 24 марта 2017 г. Специальный союз по Международной патентной классификации (Союз МПК) Комитет экспертов Сорок девятая сессия Женева, 22 и 23 февраля 2017 г. ОТЧЕТ принят Комитетом экспертовВВЕДЕНИЕ Сорок девятая сессия Комитета экспертов Союза МПК (именуемого далее "Ком...»

«Антонимы Антонимы — слова одной и той же части речи, имеющие соотносительные друг с другом противоположные значения.В этом определении важно обратить внимание на следующее:1) антонимами называются слова одной и той же части речи, поэтому не будут антонимами...»

«ИНСТРУКЦИЯ № 37 ПО ОХРАНЕ ЖИЗНИ И ЗД УТВЕРЖДАЮ: Заведующий МКДОУ детский сад "Солнышко" Сидор Н.Ф ""20_г. Инструкция По охране труда, жизни и здоровья детей1.Правила, изложенные в данной инструкции, обязательны для выполнениявсеми сотрудниками ДОУ, в особенности воспитателями и лица...»








 
2017 www.ru.i-docx.ru - «Бесплатная электронная библиотека - электронные документы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.