- Расширенные сети автоматов (arXiv)
Автор: Флориан Бриду, Максимилиан Гадуло, Гийом Тиссье.
Аннотация: Сеть автоматов — это карта f:Qn→Qn, где Q — конечный алфавит. Его можно рассматривать как сеть из n объектов, каждый из которых имеет состояние из Q и развивается в соответствии с детерминированным правилом синхронного обновления таким образом, что каждый объект зависит только от своих соседей в графе сети, называемом графом взаимодействия. Основной тенденцией в теории сетей автоматов является понимание того, как граф взаимодействия влияет на динамические свойства f. В этой работе мы вводим следующее свойство, называемое экспансивностью: наблюдения последовательности состояний в любом заданном узле достаточно, чтобы определить начальную конфигурацию всей сети. Наш основной результат — характеристика графов взаимодействия, которые допускают расширяемость. Более того, мы показываем, что это свойство является общим среди сетей линейных автоматов над такими графами с достаточно большим алфавитом. Мы показываем, однако, что ситуация усложняется, когда алфавит фиксируется независимо от размера графа взаимодействия: никакого алфавита недостаточно для получения расширяемости на всех допустимых графах, и в некоторых случаях существуют только нелинейные решения. Наконец, среди других результатов мы рассматриваем более сильную версию экспансивности, где мы просим определить начальную конфигурацию из любого достаточно большого наблюдения за системой. Мы показываем, что это может быть достигнуто для любого числа узлов и, естественно, приводит к кодам, разделяемым на максимальном расстоянии.
2. Эвристика для проблемы достижимости в асинхронных сетях с бинарными автоматами (arXiv)
Автор: Xinwei Chai, Morgan Magnin, Olivier Roux.
Аннотация: В связи с потребностью в эффективном анализе достижимости из-за неизбежной сложности крупномасштабных биологических моделей эта статья посвящена новому подходу: PermReach, для проблемы достижимости нашей новой структуры, асинхронных сетей бинарных автоматов (ABAN). ABAN — это выразительная среда моделирования, которая содержит все динамические поведения, выполняемые асинхронными булевыми сетями. По сравнению с булевыми сетями (BN) ABAN имеет более точное описание переходов состояний (из локального состояния в другое вместо симметричных булевых функций). Для анализа свойств достижимости на крупномасштабных моделях (например, из системной биологии) в предыдущих работах был продемонстрирован эффективный метод абстракции, называемый локальным графом причинности (LCG). Однако этот метод может быть не окончательным. Наш вклад здесь заключается в том, чтобы расширить эти результаты, решая эти сложные неразрешимые случаи с помощью эвристического метода. Чтобы проверить наш метод, были проведены тесты в крупных биологических сетях, показавшие, что наш метод является более убедительным, чем существующие.
