5.16. Случайная динамика для конфигураций
До сих пор мы изучали статическую случайность в пространстве конфигураций и индуцированные меры на алгебрах изображений. Следующий шаг исследований заключается в том, чтобы позволить мерам
на
зависеть от времени 1.
Конфигурация может быть описана своим составом
и соединителем с. Динамика может, например, заключаться в том, что при фиксированном составе соединения раскрываются и замыкаются на множестве
всех регулярных конфигураций, построение которых из образующих
дозволено правилами
С другой стороны, мы будем иногда встречаться с конфигурациями, у которых соединитель о фиксирован по отношению к заданным остовам образующих
но где выбор образующих варьируется со временем. Конечно, возможны и комбинации этих случаев, когда и состав, и соединитель могут меняться со временем.
Во всех случаях, изученных до сих пор, с непрерывным или дискретным временем, мы получали марковский процесс на пространстве состояний
Более того, процесс обычно был типа «рождение-смерть». Это относилось к образующим, так что на
были заданы две интенсивности
Здесь
обозначает вероятность, что данная образующая
состав
будет изъята из конфигурации с на временном интервале длины
при условии, что М. позволяет такое изьятие. Аналогично,
обозначает вероятность того, что к конфигурации
с добавится новая образующая
на временном интервале
но мы также должны оговорить, может ли
присоединяться к старым образующим в с и как это может быть сделано. Например, возможно ограничение, согласно которому ни одна пара новых связей не может быть замкнута. Или для присоединения
к с нужно пользоваться каким-то определенным соединителем. В каждом конкретном случае мы это будем явно оговаривать.
Поясним сказанное на нескольких примерах. Пусть множество. образующих
конечное, тип соединения
«линейный» и отношение связей
«равенство». Положим
при произвольном
Рассмотрим регулярную конфигурацию
где
обозначает обычный линейный соединитель слева направо. Выберем некоторую образующую
с вероятностью
и присоединим ее справа, в результате чего получится конфигурация о
но только в том случае, если такая конфигурация регулярна. Другими словами, мы выбираем случайным образом
но при условии, что
В частном случае
может содержать специальный элемент, скажем,
который означает завершение процесса. Например, в синтаксически управляемых автоматных языках это означает конец вывода предложения — см. разд. 2.10 первого тома.
При тех же условиях, но, когда
«древовидный», требуется указание о том, к которой выходной связи (в старой конфигурации) входная связь новой образующей должна быть присоединена. Это можно сделать путем случайного выбора с вероятностями, зависящими от
опять, конечно, при условии, что выполняются правила
Аналогично тому, как мы пользовались интенейвностями «рождения» и «смерти» для введения новых и удаления старых образующих, введем интенсивности «рождения» и «смерти» для пар связей. Они будут функциями показателей связей
Соответствующие вероятности будут опять обусловлены регулярностью
Например, (5.16.4) может порождать на
процесс «рождения» и «смерти»
Все значения
принадлежат заданному пространству состояний и имеют один и тот же состав. Однако их топология динамически варьируется случайным образом. Она управляется
а также правилами регулярности
Отложим анализ случайной динамики до гл. 7, где будет Детально изучен типичный для этой проблемы частный случай.