Каковы практически вычислимые свойства маркированных систем переходов?

13

Я обнаружил, что маркированные переходные системы являются хорошей моделью для моего приложения, а именно есть статья о моделировании вариантов использования с использованием LTS. Вопрос в том, что можно легко доказать о LTS? Я хотел бы повторно использовать существующие решения, чтобы увидеть, являются ли они полезными для моего приложения. Я хотел бы знать, какие свойства LTS (и вариантов использования) можно легко доказать автоматически, поэтому я могу решить, есть ли практический аналог проблемы для вариантов использования.

Габриэль Щербак
источник
1
вам нужно быть более точным. Что ты хочешь доказать? Хотите автоматический инструмент для проверки свойств? Какова ваша заявка?
Дейв Кларк
@ Дэйв Кларк отредактировал
Габриэль Шербак
2
Второй результат на Googling «меченых переходных систем»: doc.ic.ac.uk/ltsa
Каве
Спасибо всем большое за вашу помощь, я не ждал такой большой помощи. Теперь мне есть что почитать, и пока я не закончу, я не могу честно принять любой ответ, если только некоторые не будут выделены голосованием. Поэтому, пожалуйста, будьте терпеливы.
Габриэль Шербак,

Ответы:

11

Формулы логики Хеннеси-Милнера очень легко доказать о меченых системах переходов. Однако эта логика достаточно невыразительна (нет способа указать свойства бесконечных путей), поэтому вам, вероятно, захочется рассмотреть некоторые ее расширения, такие как линейная временная логика. У LTL есть решаемая, но полная PSPACE проблема.

Средство проверки моделей SPIN является широко используемым инструментом для проверки свойств LTL моделей.

Нил Кришнасвами
источник
11

Еще два инструмента, дополняющих один из предложенных Neel, - это muCRL и mCRL2 . Оба набора инструментов имеют довольно широкий набор инструментов для определения LTS на разных уровнях абстракции. Инструменты визуализации пространства состояний и проверки моделей также доступны. Основной логикой является исчисление модальных высказываний , которое гораздо более выразительно, чем LTL, но все еще разрешимо. Другие полезные инструменты позволяют выполнять уменьшение пространства состояний по модулю бисимуляции, чтобы получить наименьшее представление о вашей системе.

Дэйв Кларк
источник
Я не знал, что модальное исчисление му было решаемо! Теперь я собираюсь посмотреть доказательства в вашей ссылке ...
Нил Кришнасвами
5
Пропозициональное модальное вычисление разрешимо; Я считаю, что Стрит и Эмерсон показали это в 80-х годах. Первого порядка, конечно же, нет: он завершен для первого уровня аналитической иерархии, если я помню. Кстати, мне очень нравится этот опрос Брэдфилда и Стерлинга. Я думаю, что это одно из лучших письменных объяснений теории μ- вычислений. μμ
Марк Рейтблатт
5

Чтобы расширить ответ Дейва, модальное исчисление му также связано с понятием игр с бесконечной четностью. Здесь есть очень хороший набор лекционных заметок: http://pub.ist.ac.at/gametheory/, которые представляют связь. Как примечание стороны, не только разрешимо модальное исчисление мю, это в (см. Примечания лекции).Nпсо-Nп

Обри да Кунья
источник
3
NпсоNпЕИксп
3

Свойства CTL могут быть проверены за линейное время (см. Кларк и др. ).

Давным-давно я работал в компании, где многие коллеги использовали Rulebase для проверки интегральных схем. Язык свойств PSL , он стандартизирован IEEE и является своего рода CTL на стероидах.

Раду ГРИГОРЕ
источник
Я сомневаюсь, что FRELIMO был проверен на модели с помощью CTL - вы можете исправить эту ссылку.
reinierpost
Исправлена. Может, Google Scholar изменил свои идентификаторы? Я не помню, чтобы когда-либо видел "FRELIMO".
Раду GRIGore
2

В ходе курса я познакомился с Изабель , «ассистентом по общему доказательству». Он поддерживает (полное) функциональное программирование (близкое к ML) и логику высшего порядка. Вы можете сами определить (или найти) языки для LTS и LTL и доказать теоремы о них. Я не знаю, насколько это легко, но это, безусловно, работает.

Рафаэль
источник
1
Я прочитал (одну часть) вопрос как «Какие инструменты помогают мне доказать свойства LTS?» И доказать, что помощники пришли на ум. Вы, конечно, правы, другие тоже могут выполнять эту работу, но я не могу утверждать, что они это делают, если я этого точно не знаю, не так ли?
Рафаэль
1
Раду, я интерполировал. Обратите внимание, что такие инструменты, как Изабель, имеют возможность автоматизировать доказательства, хотя они могут быть слабее в конкретном приложении (поскольку они являются общими инструментами). Они могут быть более полезными, чем специализированные инструменты, если вы хотите доказать свойства, которые эти инструменты не могут автоматически доказать.
Рафаэль
Интересно посмотреть, как термин «универсальный помощник по доказательству», который Л. Полсон ввел в 1989 году, можно интерпретировать в наши дни. Это совершенно нормально. Первоначально идея заключалась в том, чтобы иметь общую логическую основу для формирования теории типов Мартина-Лёфа недели (которая сильно изменилась в то время). Позже каркас был повторно использован для Isabelle / ZF, снова позже для Isabelle / HOL, которая сейчас является основным приложением.
Макарий
2

Если ваш фон интерпретируется как CTL через структуры Крипке, и вы ищете что-то похожее, интерпретируемое через LTS, то ACTL (CTL на основе действий) может быть интересным.

Еще в 1990 году Р. Де Никола и Ф. Ваандрагер представили ACTL как CTL на основе действийДействие против логики на основе состояний» для систем переходов , Семантика систем параллельных процессов (1990), с. 407-419). Он был дополнительно изучен в 1993 г. (Р. Де Никола, А. Фантехи, С. Гнеси, Г. Ристори: основанная на действии структура для проверки логических и поведенческих свойств параллельных систем , компьютерных сетей и систем ISDN, том 25, № 7, с. 761-778.) И совсем недавно, в 2008 г. (Р. Меолич, Т. Капус, З. Брезочник: ACTLW - логика дерева вычислений на основе действий с оператором , кроме тех , кто работает, Information Science, 178 (6) , стр. 1542-1557.)

Основная идея ACTL (не путать с подмножеством CTL с той же аббревиатурой) состоит в том, чтобы иметь такие же операторы и алгоритмы проверки моделей, как и для CTL. Более того, операторы определяются выражениями с фиксированной запятой, аналогичными тем, которые используются для CTL. Сложность (я не уверен насчет выразительности) ACTL находится где-то между HML и модальным µ-исчислением высказываний.

meolic
источник