Войти
достижимость - фундаментальная проблема, которая возникает в нескольких различных контекстах: конечное и бесконечное состояние состояние параллельные системы, вычислительные модели, такие как клеточные автоматы и сети Петри, программный анализ, дискретные и непрерывные системы, критичные по времени системы, гибридные системы, системы перезаписи, вероятностные и номинал ametric системы и открытые системы, смоделированные как игры.
В общем, проблема достижимости может быть сформулирована следующим образом:
Варианты проблемы достижимости могут возникать в результате дополнительных ограничений на начальные или конечные состояния, конкретное требование для путей достижимости, а также для итеративной достижимости или замены вопросов на анализ выигрышных стратегий в бесконечных играх или неизбежность некоторой динамики.
Обычно для фиксированного описания системы, заданного в некоторой форме (правила редукции, системы уравнений, логические формулы и т. Д.), Проблема достижимости состоит в проверке того, соответствует ли данный набор целевых состояний могут быть достигнуты, начиная с фиксированного набора начальных состояний. Набор целевых состояний может быть представлен явно или через некоторое неявное представление (например, система уравнений, набор минимальных элементов относительно некоторого упорядочения состояний). Сложные количественные и качественные характеристики часто можно свести к основным вопросам достижимости. Разрешимость и границы сложности, алгоритмические решения и эффективная эвристика - все это важные аспекты, которые следует учитывать в этом контексте. Алгоритмические решения часто основаны на различных комбинациях стратегий исследования, символических манипуляциях с наборами состояний, свойствах декомпозиции или сведении к задачам линейного программирования, и они часто выигрывают от приближений, абстракций, ускорений и эвристики экстраполяции. Специальные решения, а также решения, основанные на средствах решения ограничений общего назначения и механизмах дедукции, часто объединяются, чтобы сбалансировать эффективность и гибкость.
Серия международных конференций по проблемам достижимости, ранее известная как Семинар по проблемам достижимости, представляет собой ежегодную научную конференцию, которая собирает вместе исследователи из различных дисциплин и профессий, интересующиеся проблемами достижимости, которые возникают в алгебраических структурах, вычислительных моделях, гибридных системах, бесконечных играх, логике и проверке. Семинар пытается заполнить пробел между результатами, полученными в разных областях, но имеющих общую математическую структуру или концептуальные трудности.
