Об алгоритмах представления транзиционных систем с помощью бинарных диаграмм решений

Abstract

Под реактивной системой понимается система, состоящая из нескольких компонент-объектов, взаимодействующих между собой и с окружающей их средой. Класс реактивных систем включает операционные системы, мультипрограммные среды, параллельные и распределенные дискретные системы, дискретные системы реального времени, вычислительные сети и т. д. В данной работе описываются алгоритмы представления конечных транзиционных систем с помощью упорядоченных бинарных таблиц решений (так называемых УБДР или OBDD – ordered binary decision diagrams) и некоторые экспериментальные данные, полученные с помощью этих алгоритмов.