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

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

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

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

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

Учитывая помеченную систему перехода состояний ( $S$ , $\Lambda$ , →),где $S$ представляет собой совокупность состояний, $\Lambda$ — это набор меток, а → — это набор помеченных переходов (т. е. подмножество $S\times \Lambda \times S$ ),отношение $R\subseteq S\times S$ является симуляцией тогда и только тогда, когда для каждой пары состояний $(p,q)$ в $R$ и все метки λ в $\Lambda$ :

если $p{\overset {\lambda }{\rightarrow }}p'$ , то есть $q{\overset {\lambda }{\rightarrow }}q'$ такой, что $(p',q')\in R$

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

R^{-1}\,;\,{\overset {\lambda }{\rightarrow }}\quad {\subseteq }\quad {\overset {\lambda }{\rightarrow }}\,;\,R^{-1}

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

Набор симуляций закрыт под объединением; ^{[Примечание 1]} следовательно, предзаказ симуляции сам по себе является симуляцией. Поскольку это объединение всех симуляций, это уникальная и крупнейшая симуляция. Моделирование также закрывается при рефлексивном и транзитивном замыкании; следовательно, самая крупная симуляция должна быть рефлексивной и транзитивной. Из этого следует, что самая большая симуляция — предварительный порядок симуляции — действительно является отношением предпорядка . ^[1] Обратите внимание, что может существовать более одного отношения, которое является одновременно симуляцией и предварительным порядком; ^{[Примечание 2]} термин «предварительный заказ моделирования» относится к самому большому из них (который является расширенным набором всех остальных).

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

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

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

См. также

Примечания

^ То есть объединение двух симуляций и есть симуляция.
^ Рассмотрим отношения $\{\}$ и $\{(0,0)\}$ — каждый из них является одновременно симуляцией и предзаказом.
^ Пример см. на рис. 1 в Шампарно, Ж.-М; Кулон, Ф. (2004). «Алгоритмы приведения NFA с помощью регулярных неравенств» . Теоретическая информатика . 327 (3): 241–253. дои : 10.1016/j.tcs.2004.02.048 . ISSN 0304-3975 .

Ссылки

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

^ Милнер, Робин (1989). Коммуникация и параллелизм . Prentice-Hall, Inc. США: ISBN 0131149849 .

[1] То есть объединение двух симуляций и есть симуляция.

[3] Рассмотрим отношения $\{\}$ и $\{(0,0)\}$ — каждый из них является одновременно симуляцией и предзаказом.

[4] Пример см. на рис. 1 в Шампарно, Ж.-М; Кулон, Ф. (2004). «Алгоритмы приведения NFA с помощью регулярных неравенств» . Теоретическая информатика . 327 (3): 241–253. дои : 10.1016/j.tcs.2004.02.048 . ISSN 0304-3975 .

[2] Милнер, Робин (1989). Коммуникация и параллелизм . Prentice-Hall, Inc. США: ISBN 0131149849 .

[Примечание 1]

[1]

[Примечание 2]

[Примечание 3]