Логика дерева вычислений
-
Основы логики дерева вычислений (CTL)
- CTL — это логика для описания свойств бесконечных путей вычислений в моделях.
- Она включает в себя операторы для описания свойств пути, такие как «всегда» (A) и «для всех» (E).
- CTL является расширением логики первого порядка, добавляя квантификаторы для описания бесконечных путей.
-
Семантика и аксиомы CTL
- Семантика CTL основана на деревьях вычислений, где каждый путь имеет начальное состояние и конечное состояние.
- Аксиомы CTL включают в себя свойства пути, такие как «существует путь, начинающийся в состоянии s и заканчивающийся в состоянии t».
-
Правила и эквивалентности CTL
- Правила CTL описывают свойства путей вычислений, такие как «для каждого пути существует состояние, в котором он заканчивается».
- Семантические эквивалентности позволяют сравнивать формулы CTL, показывая их эквивалентность в смысле удовлетворения состояниями.
-
Законы расширения и примеры
- Законы расширения позволяют расширять проверку CTL-коннекторов по отношению к их преемникам во времени.
- Примеры показывают разницу между CTL и CTL*, демонстрируя, что оператор until может не соответствовать никакому оператору path.
-
Отношения с другими логиками
- CTL является подмножеством CTL*, модального μ-исчисления и темпоральной логики Alur, Хенцингера и Купфермана с переменным временем (ATL).
- CTL и LTL являются подмножествами CTL*, но не эквивалентны, и у них есть общее подмножество.
-
Расширения CTL
- CTL был расширен за счет количественной оценки второго порядка к количественной логике вычислительного дерева (QCTL).
- Существуют две семантики QCTL: семантика дерева и семантика QCTL*.
- Пересказана только часть статьи. Для продолжения перейдите к чтению оригинала.