Моделирование (информатика) - Simulation (computer science)

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

Интуитивно система имитирует другую систему, если она может соответствовать всем своим ходам.

Основное определение связывает состояния в одной системе переходов, но это легко адаптируется для связи двух отдельных систем переходов путем построения системы, состоящей из несвязного объединения соответствующих компонентов.

Формальное определение

Учитывая маркировано состояние системы перехода ( , , →), где находится множество состояний, представляет собой набор наклеек и → представляет собой набор помеченных переходов (т.е. подмножество ), отношение является моделированием тогда и только тогда для каждой пары состояния в и все метки α в : ${\ displaystyle S}$${\ displaystyle \ Lambda}$${\ displaystyle S}$${\ displaystyle \ Lambda}$${\ Displaystyle S \ times \ Lambda \ times S}$${\ Displaystyle R \ substeq S \ times S}$ ${\ displaystyle (p, q)}$${\ displaystyle R}$${\ displaystyle \ Lambda}$

если , то существует такое, что${\ displaystyle p {\ overset {\ alpha} {\ rightarrow}} p '}$${\ displaystyle q {\ overset {\ alpha} {\ rightarrow}} q '}$${\ displaystyle (p ', q') \ in R}$

Эквивалентно с точки зрения реляционной композиции :

${\ Displaystyle R ^ {- 1} \,; \, {\ overset {\ alpha} {\ rightarrow}} \ quad {\ substeq} \ quad {\ overset {\ alpha} {\ rightarrow}} \,; \ , R ^ {- 1}}$

Даны два состояния и in , имитирует , записывается , если существует такая симуляция , что . Отношение называется предварительным порядком моделирования и представляет собой объединение всех имитаций: именно тогда, когда для некоторой симуляции . ${\ displaystyle p}$${\ displaystyle q}$${\ displaystyle S}$${\ displaystyle p}$ ${\ displaystyle q}$${\ Displaystyle п \, \ leq \, q}$${\ displaystyle R}$${\ displaystyle (p, q) \ in R}$${\ displaystyle \ leq}$${\ Displaystyle (п, д) \ в \, \ Leq \,}$${\ displaystyle (p, q) \ in R}$${\ displaystyle R}$

Множество симуляций замыкается на объединение; следовательно, предварительный заказ на симуляцию сам по себе является симуляцией. Поскольку это объединение всех симуляций, это уникальная самая большая симуляция. Моделирование также закрывается рефлексивным и транзитивным замыканием; следовательно, самая большая симуляция должна быть рефлексивной и транзитивной. Из этого следует, что самая большая симуляция - предварительный заказ моделирования - действительно является отношением предварительного заказа . Обратите внимание, что может быть более одного отношения, которое является одновременно моделированием и предварительным заказом; термин предварительный заказ моделирования относится к самому большому из них (который является надмножеством всех остальных).

Два состояния и называются подобными , записываются , если и только если имитирует и моделирует . Таким образом, подобие - это максимальное симметричное подмножество предварительного порядка моделирования, что означает, что оно рефлексивно, симметрично и транзитивно; отсюда отношение эквивалентности . Однако это не обязательно симуляция, и именно в тех случаях, когда это не симуляция, она строго грубее, чем двойное сходство (то есть это надмножество двойного сходства). Чтобы засвидетельствовать, рассмотрим подобие, которое является симуляцией. Поскольку он симметричен, это бизимуляция . Тогда это должно быть подмножество двойного сходства, которое представляет собой объединение всех двойных симуляций. Тем не менее, легко увидеть, что сходство всегда является надмножеством двойного сходства. Из этого следует, что если подобие симуляция, оно равно двойному сходству. И если оно равно двойному сходству, это, естественно, симуляция (поскольку двойное сходство - это симуляция). Следовательно, подобие является симуляцией тогда и только тогда, когда оно равно двойному сходству. Если нет, то это должен быть его строгий надмножество; отсюда и строго более грубое отношение эквивалентности. ${\ displaystyle p}$${\ displaystyle q}$${\ displaystyle p \ leq \ geq q}$${\ displaystyle p}$${\ displaystyle q}$${\ displaystyle q}$${\ displaystyle p}$

Сходство отдельных переходных систем

При сравнении двух различных систем переходов (S ', Λ', → ') и (S ", Λ", → ") можно использовать основные понятия моделирования и подобия, формируя непересекающуюся композицию двух машин (S , Λ, →) с S = S '∐ S ", Λ = Λ' ∪ Λ" и → = → '∪ → ", где ∐ - оператор несвязного объединения множеств.

Смотрите также

• Система перехода состояний
• Бисимуляция
• Коиндукция
• Операционная семантика

Рекомендации

1. Парк, Дэвид (1981). «Параллелизм и автоматы в бесконечных последовательностях» (PDF) . В Деуссене, Питер (ред.). Материалы 5-й конференции GI, Карлсруэ . Конспект лекций по информатике . 104 . Springer-Verlag . С. 167–183. DOI : 10.1007 / BFb0017309 . ISBN 978-3-540-10576-3.
2. ван Глаббек, Р.Дж. (2001). "Линейное время - ветвящийся временной спектр I: семантика конкретных, последовательных процессов". Справочник по алгебре процессов . Эльзевир. С. 3–99.