В теоретической информатике моделирование представляет собой соотношение между государственными системами переходной ассоциирующих системами , которые ведут себя таким же образом , в том смысле , что система имитирует другие.
Интуитивно система имитирует другую систему, если она может соответствовать всем своим ходам.
Основное определение связывает состояния внутри одной системы переходов, но это легко адаптируется для связи двух отдельных систем переходов путем построения системы, состоящей из несвязного объединения соответствующих компонентов.
Формальное определение
Учитывая помеченную систему перехода состояний (, , →), где это набор состояний, - это набор меток, а → - это набор помеченных переходов (т. е. подмножество ) соотношение является симуляцией тогда и только тогда, когда для каждой пары состояний в и все метки α в :
- если , то есть такой, что
Эквивалентно с точки зрения реляционной композиции :
Учитывая два состояния а также в , имитирует , написано , если есть моделирование такой, что . Соотношениеназывается предварительным заказом симуляции и представляет собой объединение всех симуляций: именно когда для некоторой симуляции .
Набор симуляций замыкается на объединение; [Примечание 1] поэтому предварительный заказ моделирования сам по себе является имитацией. Поскольку это объединение всех симуляций, это самая большая симуляция. Моделирование также закрывается рефлексивным и транзитивным замыканием; следовательно, самая большая симуляция должна быть рефлексивной и транзитивной. Из этого следует, что самая большая симуляция - предзаказ симуляции - действительно является отношением предпорядка . [1] Обратите внимание, что может быть более одного отношения, которое является одновременно моделированием и предварительным порядком; [Примечание 2] термин « предварительный заказ моделирования» относится к самому большому из них (который является надмножеством всех остальных).
Два государства а также называются подобными , написано, если и только если имитирует а также имитирует . Таким образом, подобие - это максимальное симметричное подмножество предварительного порядка моделирования, что означает, что оно рефлексивно, симметрично и транзитивно; следовательно, отношение эквивалентности . Однако это не обязательно симуляция, и именно в тех случаях, когда это не симуляция, она строго грубее, чем двойное сходство (то есть это надмножество двойного сходства). [Примечание 3] Чтобы увидеть, рассмотрим подобие, которое является симуляцией. Будучи эквивалентностью, она также симметрична и, следовательно, является бисимуляцией. Тогда это должно быть подмножество двойного сходства, которое является объединением всех двойных симуляций. Тем не менее легко увидеть, что сходство всегда является надмножеством двойного сходства. Из этого следует, что если подобие симуляция, оно равно двойному сходству. И если это равносильно двойному сходству, это, естественно, симуляция; следовательно, подобие является симуляцией, если оно равно двойному сходству. Если нет, то это должен быть его строгий надмножество; отсюда и строго более грубое отношение эквивалентности.
- ^ Это означает, что объединение двух симуляций является симуляцией.
- ^ Рассмотрим отношения а также - каждая из них является одновременно симуляцией и предзаказом.
- ^ Для примера см. Рис. 1 в Champarnaud, J.-M; Кулон, Ф. (2004). «Алгоритмы редукции NFA с помощью регулярных неравенств» . Теоретическая информатика . 327 (3): 241–253. DOI : 10.1016 / j.tcs.2004.02.048 . ISSN 0304-3975 .
Сходство отдельных переходных систем
При сравнении двух различных систем переходов (S ', Λ', → ') и (S ", Λ", → ") можно использовать основные понятия моделирования и подобия, формируя непересекающуюся композицию двух машин (S , Λ, →) с S = S '∐ S ", Λ = Λ' ∪ Λ" и → = → '∪ → ", где ∐ - оператор несвязного объединения множеств.
Смотрите также
Рекомендации
- Парк, Дэвид (1981). «Параллелизм и автоматы в бесконечных последовательностях» (PDF) . В Деуссене, Питер (ред.). Материалы 5-й конференции GI, Карлсруэ . Конспект лекций по информатике . 104 . Springer-Verlag . С. 167–183. DOI : 10.1007 / BFb0017309 . ISBN 978-3-540-10576-3.
- ван Глаббек, Р.Дж. (2001). «Линейное время - ветвящийся временной спектр I: семантика конкретных, последовательных процессов». Справочник по алгебре процессов . Эльзевир. С. 3–99.