В проверке модели , поле информатики , Timed Пропозициональное Temporal Logic ( TPTL ) является продолжением линейной темпоральной логики (LTL) , в котором введены переменных для измерения времени между двумя событиями. Например, в то время как LTL позволяет утверждать, что за каждым событием p в конечном итоге следует событие q , TPTL, кроме того, позволяет указать предел времени для возникновения q .
Синтаксис
Фрагмент будущего TPTL определяется аналогично линейной временной логики , в котором , кроме того, часы переменные могут быть введены и по сравнению с константами. Формально, учитывая набор часов MTL состоит из:
- конечный набор пропозициональных переменных AP ,
- эти логические операторы ¬ и ∨, и
- временнымы модальный оператор U ,
- сравнение часов , с участием , число и оператор сравнения, такой как <, ≤, =, ≥ или>.
- оператор квантификации замораживания , для формула TPTL с набором часов .
Кроме того, для интервал, считается аббревиатурой для ; и то же самое для всех других видов интервалов.
Логика TPTL + Past [1] построена как будущий фрагмент TLS и также содержит
- временный модальный оператор S .
Обратите внимание, что следующий оператор N не считается частью синтаксиса MTL. Вместо этого он будет определяться другими операторами.
Замкнутая формула является формулой над пустым множеством часов. [2]
Модель
Позволять он интуитивно представляет собой набор времени. Позволять функция, которая ассоциируется с каждым моментом набор предложений от AP . Модель формулы TPTL - это такая функция. Обычно,является либо синхронизированным словом, либо сигналом . В таких случаях является либо дискретным подмножеством, либо интервалом, содержащим 0.
Семантический
Позволять а также как указано выше. Позволятьнабор часов . Позволять оценка часов закончилась .
Теперь мы собираемся объяснить, что означает, что формула TPTL держится на время для оценки . Это обозначается. Позволять а также две формулы над набором часов , формула по набору часов , , , число и оператор сравнения, такой как <, ≤, =, ≥ или>: сначала рассмотрим формулы, главный оператор которых также принадлежит LTL:
- имеет место, если ,
- имеет место, если либо или же
- имеет место, если либо или же
- выполняется, если существует такой, что и такой, что для каждого , ,
- выполняется, если существует такой, что и такой, что для каждого , ,
- имеет место, если держит,
- имеет место, если .
Метрическая темпоральная логика
Метрическая темпоральная логика - это еще одно расширение LTL, которое позволяет измерять время. Вместо добавления переменных он добавляет бесконечное количество операторов. а также для интервал неотрицательного числа. Смысл формулы в какой-то момент по сути совпадает с семантикой формулы , с ограничениями, что время на котором должен удерживаться происходит в интервале .
TPTL не менее выразителен, чем MTL. Действительно, формула MTL эквивалентно формуле TPTL где это новая переменная. [2]
Отсюда следует, что любой другой оператор, введенный в MTL страницы , например а также также могут быть определены как формулы TPTL.
TPTL строго более выразителен, чем MTL [1] : 2 как для синхронизированных слов, так и для сигналов. Для слов, рассчитанных по времени, никакая формула MTL не эквивалентна. По сигналу нет формулы MTL, эквивалентной, в котором говорится, что последнее атомарное предложение перед моментом времени 1 является .
Сравнение с LTL
Стандартное (бессрочное) бесконечное слово это функция от к . Мы можем рассмотреть такое слово, используя набор времени, а функция . В этом случае для произвольная формула LTL, если и только если , где рассматривается как формула TPTL с нестрогим оператором, а - единственная функция, определенная на пустом наборе.
Рекомендации
- ^ a b Буйе, Патрисия ; Шевалье, Фабрис; Марки, Николас (2005). «О выразительности TPTL и MTL» . Материалы 25-й конференции по основам программных технологий и теоретической информатики : 436. doi : 10.1007 / 11590156_3 .
- ^ а б Алур, Раджив; Хенцингер, Томас А. (январь 1994 г.). «Действительно временная логика». Журнал ACM . 41 (1): 181–203. DOI : 10.1145 / 174644.174651 .