под ред. д.ф.-м.н. В.Н. Касьянова
Новосибирск 2007
Теория параллельных систем и процессов - активно развивающийся раздел компьютерных наук, в задачу которого входит разработка и исследование формальных моделей для спецификации и анализа систем с независимой работой компонентов. Среди таких моделей наибольшую известность приобрели сети Петри (СП) и процессные алгебры (ПА). Понятие эквивалентности - важнейшее понятие теории вычислительных процессов. Поведенческие эквивалентности позволяют сравнивать системы с учетом различных аспектов их функционирования. Бисимуляционная эквивалентность является, на сегодняшний день, одним из самых популярных отношений, используемых для сопоставления поведения систем и процессов. В монографии разработан и исследован широкий спектр поведенческих (в том числе и бисимуляционных) эквивалентностей для СП и ПА, а также для подклассов и расширений этих моделей.
В книге представлены следующие результаты.
- На СП с видимыми и невидимыми переходами и их подклассах введен и изучен большой набор базисных, обратных-прямых и учитывающих места поведенческих эквивалентностей в семантиках от интерливинговой до истинного параллелизма и от линейного до ветвистого времени.
- На временных сетях Петри с видимыми и невидимыми переходами и их подклассах разработан и исследован ряд временных, не-временных и региональных интерливинговых эквивалентностей в следовой и бисимуляционной семантиках.
- На стохастических сетях Петри с невидимыми переходами определен и изучен ряд базисных, обратных и обратных-прямых эквивалентностей в интерливинговой и шаговой, а также в следовой и бисимуляционной семантиках.
- Исследованы семантические эквивалентности стандартных и стохастических ПА, а также их связь с сетевыми эквивалентностными отношениями. Разработан и реализован алгоритм автоматической проверки семантической эквивалентности формул.
Монография предназначена студентам, аспирантам и исследователям, интересующимся теоретической информатикой, в частности, формальным моделированием и анализом свойств поведения параллельных систем и процессов.
Ключевые слова: обычные, временные и стохастические сети Петри, подклассы, обычные и стохастические процессные алгебры, невидимые переходы и действия, поведенческие и семантические эквивалентности, бисимуляция, темпоральные и вероятностные логики, редукция, детализация и композиция, конгруэнтность, аксиоматизация, системы переписывания термов, программная реализация.
Книгу можно приобрести в интернет-магазине Издательства СО РАН или в книжном магазине Академкнига (г. Новосибирск, Морской пр-т, д. 22, телефон: (383) 330-0922).