Стохастический клеточный автомат

Стохастические клеточные автоматы или вероятностные клеточные автоматы ( PCA ), или случайные клеточные автоматы , или локально взаимодействующие цепи Маркова. ^[1]^[2] являются важным расширением клеточного автомата . с дискретным временем Клеточные автоматы представляют собой динамическую систему взаимодействующих сущностей , состояние которой дискретно.

Состояние коллекции сущностей обновляется в каждый дискретный момент времени согласно некоторому простому однородному правилу. Состояния всех сущностей обновляются параллельно или синхронно. Стохастические клеточные автоматы — это CA, правило обновления которых является стохастическим , что означает, что состояния новых объектов выбираются в соответствии с некоторыми распределениями вероятностей. Это случайная динамическая система с дискретным временем . Из пространственного взаимодействия между сущностями, несмотря на простоту правил обновления, сложное поведение может возникнуть типа самоорганизации . Как математический объект его можно рассматривать в рамках стохастических процессов как взаимодействующую систему частиц в дискретном времени.Видеть ^[3]для более подробного ознакомления.

PCA как марковские стохастические процессы

Как марковский процесс с дискретным временем, PCA определяются в пространстве произведений. $E=\prod _{k\in G}S_{k}$ (декартово произведение), где $G$ является конечным или бесконечным графом, например $\mathbb {Z}$ и где $S_{k}$ это конечное пространство, как, например, $S_{k}=\{-1,+1\}$ или $S_{k}=\{0,1\}$ . Вероятность перехода имеет вид произведения $P(d\sigma |\eta )=\otimes _{k\in G}p_{k}(d\sigma _{k}|\eta )$ где $\eta \in E$ и $p_{k}(d\sigma _{k}|\eta )$ представляет собой распределение вероятностей на $S_{k}$ .В общем, требуется некоторая локальность $p_{k}(d\sigma _{k}|\eta )=p_{k}(d\sigma _{k}|\eta _{V_{k}})$ где $\eta _{V_{k}}=(\eta _{j})_{j\in V_{k}}$ с ${V_{k}}$ конечная окрестность k. Видеть ^[4] для более подробного введения с точки зрения теории вероятностей.

Примеры стохастического клеточного автомата

Большинство клеточных автоматов

Существует версия мажоритарного клеточного автомата с вероятностными правилами обновления. См. правило Тоума .

Связь с решетчатыми случайными полями

может использоваться для моделирования Изинга модели ферромагнетизма PCA в статистической механике . ^[5]Некоторые категории моделей изучались с точки зрения статистической механики.

Модель сотовой связи Поттса

Существует сильная связь ^[6]между вероятностными клеточными автоматами и клеточной моделью Поттса, в частности, когда она реализуется параллельно.

Ссылки

^ Тоом, А.Л. (1978), Локально взаимодействующие системы и их применение в биологии: Материалы школы-семинара по марковским процессам взаимодействия в биологии, проходившего в Пущино, март 1976 г. , Конспект лекций по математике, т. 1, с. 653, Springer-Verlag, Берлин-Нью-Йорк, ISBN 978-3-540-08450-1 , МР 0479791
^ Р.Л. Добрушин; В.И. Крищуков; А.Л. Тоом (1978). Стохастические клеточные системы: эргодичность, память, морфогенез . Издательство Манчестерского университета. ISBN 9780719022067 .
^ Фернандес, Р.; Луи, П.-Ю.; Нарди, Франция (2018). «Глава 1: Обзор: модели и проблемы PCA». В Луи, П.-Ю.; Нарди, Франция (ред.). Вероятностные клеточные автоматы . Спрингер. дои : 10.1007/978-3-319-65558-1_1 . ISBN 9783319655581 . S2CID 64938352 .
^ П.-Ю. Луи, доктор философии
^ Вичняк, Г. (1984), «Моделирование физики с помощью клеточных автоматов», Physica D , 10 (1–2): 96–115, Bibcode : 1984PhyD...10...96V , doi : 10.1016/0167-2789( 84)90253-7 .
^ Боас, Соня ЭМ; Цзян, И; Меркс, Руланд М.Х.; Прокопиу, Сотирис А.; Ренс, Элизабет Г. (2018). «Глава 18: Клеточная модель Поттса: приложения к васкулогенезу и ангиогенезу». В Луи, П.-Ю.; Нарди, Франция (ред.). Вероятностные клеточные автоматы . Спрингер. дои : 10.1007/978-3-319-65558-1_18 . hdl : 1887/69811 . ISBN 9783319655581 .

Дальнейшее чтение

Алмейда, РМ; Макао, EEN (2010), «Модель стохастических клеточных автоматов для динамики распространения лесных пожаров», 9-я Бразильская конференция по динамике, управлению и их приложениям, 7–11 июня 2010 г. , том. 285, с. 012038, номер документа : 10.1088/1742-6596/285/1/012038 .
Кларк, КК; Хоппен, С. (1997), «Самомодифицирующаяся клеточно-автоматная модель исторической урбанизации в районе залива Сан-Франциско» (PDF) , Environment and Planning B: Planning and Design , 24 (2): 247–261, Bibcode : 1997EnPlB..24..247C , номер документа : 10.1068/b240247 , S2CID 40847078 .
Махаджан, Мина Бхаскар (1992), Исследования языковых классов, определяемых различными типами изменяющихся во времени клеточных автоматов , доктор философии. диссертация, Индийский технологический институт Мадраса .
Нисио, Хиденосукэ; Кобучи, Юичи (1975), «Отказоустойчивые клеточные пространства», Журнал компьютерных и системных наук , 11 (2): 150–170, doi : 10.1016/s0022-0000(75)80065-1 , MR 0389442 .
Смит, Элви Рэй III (1972), «Распознавание языка в реальном времени с помощью одномерных клеточных автоматов», Журнал компьютерных и системных наук , 6 (3): 233–253, doi : 10.1016/S0022-0000(72)80004 -7 , МР 0309383 .
Луи, П.-Ю.; Нарди, Франция, ред. (2018). Вероятностные клеточные автоматы . Возникновение, сложность и вычисление. Том. 27. Спрингер. дои : 10.1007/978-3-319-65558-1 . hdl : 2158/1090564 . ISBN 9783319655581 .
Агапие, А.; Андреица, А.; Джуклеа, М. (2014), «Вероятностные клеточные автоматы», Журнал вычислительной биологии , 21 (9): 699–708, doi : 10.1089/cmb.2014.0074 , PMC 4148062 , PMID 24999557

[1] Тоом, А.Л. (1978), Локально взаимодействующие системы и их применение в биологии: Материалы школы-семинара по марковским процессам взаимодействия в биологии, проходившего в Пущино, март 1976 г. , Конспект лекций по математике, т. 1, с. 653, Springer-Verlag, Берлин-Нью-Йорк, ISBN 978-3-540-08450-1 , МР 0479791

[2] Р.Л. Добрушин; В.И. Крищуков; А.Л. Тоом (1978). Стохастические клеточные системы: эргодичность, память, морфогенез . Издательство Манчестерского университета. ISBN 9780719022067 .

[IntroPCA-3] Фернандес, Р.; Луи, П.-Ю.; Нарди, Франция (2018). «Глава 1: Обзор: модели и проблемы PCA». В Луи, П.-Ю.; Нарди, Франция (ред.). Вероятностные клеточные автоматы . Спрингер. дои : 10.1007/978-3-319-65558-1_1 . ISBN 9783319655581 . S2CID 64938352 .

[4] П.-Ю. Луи, доктор философии

[vichniac-5] Вичняк, Г. (1984), «Моделирование физики с помощью клеточных автоматов», Physica D , 10 (1–2): 96–115, Bibcode : 1984PhyD...10...96V , doi : 10.1016/0167-2789( 84)90253-7 .

[CPM-6] Боас, Соня ЭМ; Цзян, И; Меркс, Руланд М.Х.; Прокопиу, Сотирис А.; Ренс, Элизабет Г. (2018). «Глава 18: Клеточная модель Поттса: приложения к васкулогенезу и ангиогенезу». В Луи, П.-Ю.; Нарди, Франция (ред.). Вероятностные клеточные автоматы . Спрингер. дои : 10.1007/978-3-319-65558-1_18 . hdl : 1887/69811 . ISBN 9783319655581 .

[1]

[2]

[3]

[4]

[5]

[6]