Метрическая темпоральная логика - Metric temporal logic

Метрическая темпоральная логика (MTL) - это частный случай темпоральная логика. Это расширение временной логики, в которой временные операторы заменены версиями с ограничением по времени, такими как до того как, следующий, поскольку и предыдущий операторы. Это логика линейного времени, которая предполагает и чередование, и абстракции фиктивных часов. Он определен на основе точечной слабо-монотонной целочисленной семантики. Для MTL точная сложность задач выполнимости известна и не зависит от интервальной или точечной, синхронной (т. Е. Строго монотонной) или асинхронной (т. Е. Слабо-монотонной) интерпретации: EXPSPACE-complete.^[1]

MTL был описан как выдающийся формализм спецификации для систем реального времени.^[2] Полный MTL для бесконечных синхронизированных слов неразрешим.^[3]

Синтаксис

В полная метрическая темпоральная логика определяется аналогично линейная темпоральная логика, где набор неотрицательных действительных чисел добавляется к временный модальные операторы U и S. Формально MTL состоит из:

• конечный набор пропозициональные переменные AP,
• то логические операторы ¬ и ∨, и
• то временный модальный оператор U_я (произносится "${ displaystyle phi}$ пока в ${ displaystyle I}$ ${ displaystyle psi}$."), с _я интервал неотрицательного числа.
• то временный модальный оператор S_я (произносится "${ displaystyle phi}$ поскольку в ${ displaystyle I}$ ${ displaystyle psi}$."), с _я как указано выше.

Когда нижний индекс опущен, он неявно равен ${ displaystyle [0, infty)}$.

Обратите внимание, что следующий оператор N не считается частью синтаксиса MTL. Вместо этого он будет определяться другими операторами.

Прошлое и будущее

В прошлый фрагмент метрической темпоральной логики, обозначенный как прошлое MTL определяется как ограничение полной темпоральной логики метрики без оператора до. Точно так же будущий фрагмент метрической темпоральной логики, обозначенный как будущее-MTL определяется как ограничение полной метрической темпоральной логики без оператора Since.

В зависимости от авторов, MTL либо определяется как будущий фрагмент MTL, и в этом случае полный MTL называется MTL + Прошлое.^[2][4] Или же MTL определяется как полный MTL.

Во избежание двусмысленности в этой статье используются имена full-MTL, past-MTL и future-MTL. Когда утверждения выполняются для трех логических схем, будет просто использоваться MTL.

Модель

Позволять ${ Displaystyle Т substeq mathbb {R} _ {+}}$ интуитивно представить набор моментов времени. Позволять ${ displaystyle gamma: T to A}$ функция, которая связывает букву с каждым моментом ${ displaystyle t in T}$. Модель формулы MTL представляет функцию ${ displaystyle gamma}$. Обычно, ${ displaystyle gamma}$ это либо синхронизированное слово или сигнал. В этих случаях ${ displaystyle T}$ является либо дискретным подмножеством, либо интервалом, содержащим 0.

Семантика

Позволять ${ displaystyle T}$ и ${ displaystyle gamma}$ как указано выше, и пусть ${ displaystyle t in T}$ какое-то фиксированное время. Теперь мы собираемся объяснить, что означает, что формула MTL ${ displaystyle phi}$ держится на время ${ displaystyle t}$, который обозначается ${ displaystyle gamma, т модели phi}$.

Позволять ${ Displaystyle I substeq mathbb {R} _ {+}}$ и ${ displaystyle phi, psi in MTL}$. Рассмотрим сначала формулу ${ displaystyle phi { mathcal {U}} _ {I} psi}$. Мы говорим, что ${ displaystyle gamma, т модели phi { mathcal {U}} _ {I} psi}$ если и только если существует какое-то время ${ displaystyle t ' in I + t}$ такой, что:

• ${ displaystyle gamma, т ' модели psi}$ и
• для каждого ${ displaystyle t '' in T}$ с ${ Displaystyle т <т '' <т '}$, ${ displaystyle gamma, т '' модели phi}$.

Теперь рассмотрим формулу ${ displaystyle phi { mathcal {S}} _ {I} psi}$ (произносится "${ displaystyle phi}$ так как ${ displaystyle I}$ ${ displaystyle psi}$. ") Мы говорим, что ${ Displaystyle gamma, т модели phi { mathcal {S}} _ {I} psi}$ если и только если существует какое-то время ${ displaystyle t ' in I-t}$ такой, что:

• ${ displaystyle gamma, т ' модели psi}$ и
• для каждого ${ displaystyle t '' in T}$ с ${ Displaystyle т '<т' '<т}$, ${ Displaystyle gamma, т '' модели phi}$.

Определения ${ displaystyle gamma, т модели phi}$ для ценностей ${ displaystyle phi}$ не рассмотренный выше аналогично определению в LTL дело.

Операторы, определенные из основных операторов MTL

Некоторые формулы используются настолько часто, что для них вводится новый оператор. Эти операторы обычно не относятся к определению MTL, но являются синтаксический сахар которые обозначают более сложную формулу MTL. Сначала рассмотрим операторы, которые также существуют в LTL. В этом разделе мы исправляем ${ displaystyle phi, psi}$ Формулы MTL и ${ Displaystyle I substeq mathbb {R} _ {+}}$.

Операторы, аналогичные LTL

Отпустить и вернуться к

Обозначим через ${ displaystyle phi { mathcal {R}} _ {I} psi}$(произносится "${ displaystyle phi}$ релизин ${ displaystyle I}$, ${ displaystyle psi}$") формула ${ displaystyle neg phi { mathcal {U}} _ {I} neg psi}$. Эта формула верна ${ displaystyle t}$ если либо:

• есть время ${ displaystyle t ' in t + I}$ такой, что ${ displaystyle phi}$ держит, и ${ displaystyle psi}$ держать в интервале ${ Displaystyle (т, т ') кепка (т + я)}$.
• каждый раз ${ displaystyle t ' in t + I}$, ${ displaystyle phi}$ держит.

Название «выпуск» происходит от случая LTL, где эта формула просто означает, что ${ displaystyle phi}$ всегда следует держать, если только ${ displaystyle psi}$ выпускает его.

Предыдущий аналог выпуска обозначается ${ displaystyle phi { mathcal {B}} _ {I} phi}$(произносится "${ displaystyle phi}$ назад к ${ displaystyle I}$, ${ displaystyle psi}$") и равен формуле ${ displaystyle neg phi { mathcal {S}} _ {I} neg phi}$.

Наконец и в конце концов

Обозначим через ${ displaystyle Diamond _ {I} phi}$ или же ${ displaystyle { mathcal {F}} _ {I} phi}$ (произносится как "Наконец-то ${ displaystyle I}$, ${ displaystyle phi}$"или" В конце концов в ${ displaystyle I}$, ${ displaystyle phi}$") формула ${ displaystyle top { mathcal {U}} _ {I} phi}$. Интуитивно эта формула верна в момент ${ displaystyle t}$если есть время ${ displaystyle t ' in t + I}$ такой, что ${ displaystyle phi}$ держит.

Обозначим через ${ displaystyle Box _ {I} phi}$ или же ${ displaystyle { mathcal {G}} _ {I} phi}$ (произносится как "Глобаллин" ${ displaystyle I}$, ${ displaystyle phi}$",) формула ${ displaystyle neg Diamond _ {I} neg phi}$. Интуитивно понятно, что эта формула время от времени ${ displaystyle t}$ если на все времена ${ displaystyle t ' in t + I}$, ${ displaystyle phi}$ держит.

Обозначим через ${ displaystyle { overleftarrow { Box}} _ {I} phi}$и ${ displaystyle { overleftarrow { Diamond}} _ {I} phi}$ формула, аналогичная ${ displaystyle Box _ {I} phi}$ и ${ displaystyle Diamond _ {I} phi}$,куда ${ displaystyle { mathcal {U}}}$ заменяется на ${ Displaystyle { mathcal {S}}}$. Обе формулы интуитивно имеют одинаковое значение, но когда мы рассматриваем прошлое, а не будущее.

Следующее и предыдущее

Этот случай немного отличается от предыдущих, поскольку интуитивное значение формул «Далее» и «Ранее» различается в зависимости от типа функции. ${ displaystyle gamma}$ считается.

Обозначим через ${ displaystyle bigcirc _ {I} phi}$ или же ${ displaystyle { mathcal {N}} _ {I} phi}$(произносится как "следующий в ${ displaystyle I}$, ${ displaystyle phi}$") формула ${ displaystyle bot { mathcal {U}} _ {I} phi}$. Аналогично обозначим через ${ displaystyle ominus _ {I} phi}$^[5] (произносится как "Ранее в ${ displaystyle I}$, ${ displaystyle phi}$) формула ${ displaystyle bot { mathcal {S}} _ {I} phi}$. Следующее обсуждение оператора Next справедливо и для оператора Previously, обращая вспять прошлое и будущее.

Когда эта формула оценивается по синхронизированное слово ${ displaystyle gamma: T to A}$, эта формула означает, что оба:

• в следующий раз в области определения ${ displaystyle T}$, формула ${ displaystyle phi}$ будет держать.
• кроме того, расстояние между этим следующим временем и текущим временем принадлежит интервалу ${ displaystyle I}$.
• В частности, это следующее время выполняется, поэтому текущее время не является концом слова.

Когда эта формула оценивается по сигнал ${ displaystyle gamma}$Понятие следующего раза не имеет смысла. Вместо этого «следующий» означает «сразу после». Точнее ${ Displaystyle gamma, т модели circ phi}$ средства:

• ${ displaystyle I}$ содержит интервал вида ${ displaystyle (0, epsilon)}$ и
• для каждого ${ Displaystyle т ' в (т, т + эпсилон)}$, ${ displaystyle gamma, т ' модели phi}$.

Другие операторы

Теперь рассмотрим операторы, не похожие ни на какие стандартные операторы LTL.

Падение и взлет

Обозначим через ${ displaystyle uparrow phi}$ (произносится "рост" ${ displaystyle phi}$"), формула, которая имеет место, когда ${ displaystyle phi}$ становится правдой. Точнее, либо ${ displaystyle phi}$ не удерживалась в ближайшем прошлом и остается в силе в настоящее время или не имеет силы и имеет место в ближайшем будущем. Формально ${ displaystyle uparrow phi}$ определяется как ${ displaystyle ( phi land ( neg phi { mathcal {S}} top)) lor ( neg phi land ( phi { mathcal {U}} top))}$.^[6]

Эта формула всегда остается верной для определенных слов. В самом деле ${ displaystyle phi { mathcal {U}} top}$ и ${ displaystyle neg phi { mathcal {S}} top}$ всегда держи. Таким образом, формула эквивалентна ${ Displaystyle фи лор нег фи}$, следовательно, верно.

В силу симметрии обозначим через ${ displaystyle downarrow phi}$ (произносится как "Падение" ${ displaystyle phi}$), формула, которая имеет место при ${ displaystyle phi}$ становится ложным. Таким образом, он определяется как ${ displaystyle ( neg phi land ( phi { mathcal {S}} top)) land ( phi land ( neg phi { mathcal {U}} top))}$.

История и пророчество

Теперь представим пророчество оператор, обозначаемый ${ displaystyle triangleright}$. Обозначим через ${ displaystyle triangleright _ {I} phi}$^[7] формула ${ displaystyle neg phi { mathcal {U}} _ {I} phi}$. Эта формула утверждает, что существует первый момент в будущем, такой что ${ displaystyle phi}$ держится, и время ждать этого первого момента принадлежит ${ displaystyle I}$.

Теперь мы рассмотрим эту формулу над синхронизированными словами и над сигналами. Сначала мы рассматриваем рассчитанные на время слова. Предположить, что ${ displaystyle I = mid a, b mid '}$ куда ${ displaystyle mid}$ и ${ displaystyle mid '}$ представляет собой открытые или закрытые границы. Позволять ${ displaystyle gamma}$ рассчитанное слово и ${ displaystyle t}$ в своей области определения. С течением времени формула ${ displaystyle gamma, т модели triangleright _ {I} phi}$ выполняется тогда и только тогда, когда ${ displaystyle gamma, t models Box _ {] 0, b [ setminus I} neg phi land Diamond _ {I} phi}$ также имеет место. То есть эта формула просто утверждает, что в будущем, пока интервал ${ displaystyle t + I}$ встречается, ${ displaystyle phi}$ не должно держаться. Более того, ${ displaystyle phi}$ должен держаться когда-нибудь в интервале ${ displaystyle t + I}$. Действительно, в любое время ${ displaystyle t '' in t + I}$ такой, что ${ Displaystyle gamma, т '' модели phi}$ держать, существует только конечное число раз ${ displaystyle t ' in t + I}$ с ${ Displaystyle т '<т' '}$ и ${ displaystyle gamma, т ' модели phi}$. Таким образом, обязательно существует меньшая такая ${ displaystyle t ''}$.

Давайте теперь рассмотрим сигнал. Вышеупомянутая эквивалентность больше не действует в отношении сигнала. Это связано с тем, что при использовании переменных, представленных выше, может существовать бесконечное количество правильных значений для ${ displaystyle t '}$, в связи с тем, что область определения сигнала непрерывна. Таким образом, формула ${ displaystyle triangleright _ {I} phi}$ также гарантирует, что первый интервал, в котором ${ displaystyle phi}$ держит закрыто слева.

По временной симметрии мы определяем история оператор, обозначаемый ${ Displaystyle треугольникleft}$. Мы определяем ${ Displaystyle треугольникleft _ {I} phi}$ в качестве ${ Displaystyle neg phi { mathcal {S}} _ {I} phi}$. Эта формула утверждает, что в прошлом существует такой последний момент, что ${ displaystyle phi}$ удерживается. И время с этого первого момента принадлежит ${ displaystyle I}$.

Нестрогий оператор

Семантика операторов до и после введения не учитывает текущее время. То есть для того, чтобы ${ Displaystyle phi _ {1} { overline { mathcal {U}}} phi _ {2}}$ держать в какое-то время ${ displaystyle t}$, ни один ${ displaystyle phi _ {1}}$ ни ${ displaystyle phi _ {2}}$ должен удерживать время ${ displaystyle t}$. Это не всегда требуется, например, в предложении «не будет ошибок до тех пор, пока система не будет выключена», на самом деле может потребоваться, чтобы в настоящее время ошибок не было. Таким образом, мы вводим еще один оператор до тех пор, пока он называется нестрогие до, обозначаемый ${ displaystyle { overline { mathcal {U}}}}$, которые учитывают текущее время.

Обозначим через ${ Displaystyle phi _ {1} { overline { mathcal {U}}} _ {I} phi _ {2}}$ и ${ Displaystyle phi _ {1} { overline { mathcal {S}}} _ {I} phi _ {2}}$ либо:

• формулы ${ displaystyle phi _ {2} lor ( phi _ {1} land ( phi _ {1} { mathcal {U}} _ {I} phi _ {2}))}$ и ${ displaystyle phi _ {2} lor ( phi _ {1} land ( phi _ {1} { mathcal {S}} _ {I} phi _ {2}))}$ если ${ displaystyle 0 in I}$, и
• формулы ${ displaystyle phi _ {1} land ( phi _ {1} { mathcal {U}} _ {I} phi _ {2})}$ и ${ displaystyle phi _ {1} land ( phi _ {1} { mathcal {S}} _ {I} phi _ {2})}$ иначе.

Для любого из операторов ${ displaystyle { mathcal {O}}}$ введенное выше, обозначим ${ displaystyle { overline { mathcal {O}}}}$ формула, в которой используются нестрогие до и грехи. Например ${ displaystyle { overline { Diamond}} p}$ это сокращение от ${ displaystyle top { overline { mathcal {U}}} p}$.

Строгий оператор не может быть определен с помощью нестрогого оператора. То есть не существует формулы, эквивалентной ${ displaystyle bigcirc _ {I} p}$ который использует только нестрогий оператор. Эта формула определяется как ${ displaystyle bot { mathcal {U}} _ {I} p}$. Эта формула никогда не может работать одновременно ${ displaystyle t}$ если требуется, чтобы ${ displaystyle bot}$ держится на время ${ displaystyle t}$.

Пример

Приведем примеры формул MTL. Еще несколько примеров можно найти в статье фрагментов MITL, таких как временная логика метрического интервала.

• ${ displaystyle Box (p подразумевает Diamond _ { {1 }} q)}$ заявляет, что каждая буква ${ displaystyle p}$ после ровно через одну единицу времени следует буква ${ displaystyle q}$.
• ${ displaystyle Box (p подразумевает neg Diamond _ { {1 }} p)}$ утверждает, что нет двух последовательных появлений ${ displaystyle p}$ могут происходить точно в одну единицу времени друг от друга.

Сравнение с LTL

Стандартное (бессрочное) бесконечное слово ${ displaystyle w = a_ {0}, a_ {1}, dots,}$ это функция от ${ Displaystyle mathbb {N}}$ к ${ displaystyle A}$. Мы можем рассматривать такое слово, используя набор времени ${ Displaystyle Т = mathbb {N}}$, а функция ${ Displaystyle гамма (я) = а_ {я}}$. В этом случае для ${ displaystyle phi}$ произвольная формула LTL, ${ Displaystyle ш, я модели phi}$ если и только если ${ displaystyle gamma, я модели phi}$, куда ${ displaystyle phi}$ рассматривается как формула MTL с нестрогим оператором и ${ displaystyle [0, infty)}$ нижний индекс. В этом смысле MTL является расширением LTL.^{[требуется разъяснение ]}

По этой причине формула, использующая только нестрогий оператор с ${ displaystyle [0, infty)}$ нижний индекс называется формулой LTL. Это потому, что^{[требуется дальнейшее объяснение ]}

Алгоритмическая сложность

Выполнимость ECL по сигналам равна EXPSPACE -полный.^[7]

Фрагменты MTL

Теперь рассмотрим некоторые фрагменты MTL.

MITL

Важным подмножеством MTL является Метрический интервал временныйЛогика (MITL). Это определяется аналогично MTL, сограничение, что множества ${ displaystyle I}$, используется в ${ displaystyle { mathcal {U}}}$ и ${ Displaystyle { mathcal {S}}}$, являются интервалами, которые не являются одиночными, и чьи границы - натуральные числа или бесконечность.

Некоторые другие подмножества MITL определены в статье MITL.

Будущие фрагменты

Future-MTL уже был представлен выше. Как для синхронизированных слов, так и для сигналов, он менее выразителен, чем Full-MTL^[4]:3.

Временная логика событий-часов

Фрагмент Временная логика событий-часов^[7] MTL, обозначенный EventClockTL или же ECL, допускает только следующие операторы:

• логические операторы and, or, not
• несвязанные до и с операторов.
• Операторы предсказания времени и истории.

Вне сигналов, ECL столь же выразителен, как MITL и как MITL₀. Эквивалентность двух последних логик объясняется в статье. MITL₀. Мы делаем набросок эквивалентности этих логик с помощью ECL.

Если ${ displaystyle I}$ не синглтон и ${ displaystyle phi}$ формула MITL, ${ displaystyle triangleright _ {I} phi}$ определяется как формула MITL. Если ${ Displaystyle I = {я }}$ синглтон, то ${ displaystyle triangleright _ {I} phi}$ эквивалентно ${ Displaystyle Box _ {] 0, я [} neg phi land Diamond _ {] 0, i]} phi}$ которая является MITL-формулой. Взаимно для ${ displaystyle psi}$ ECL-формула, и ${ displaystyle I}$ интервал, нижняя граница которого равна 0, ${ displaystyle Box _ {I} psi}$ эквивалентно ECL-формуле ${ displaystyle neg triangleright _ {I} neg psi}$.

Выполнимость ECL по сигналам равна PSPACE-полный.^[7]

Положительная нормальная форма

MTL-формула в положительной нормальной форме определяется почти как любая MTL-формула с двумя следующими изменениями:

• операторы Релиз и Назад вводятся в логическом языке и больше не считаются обозначениями для некоторых других формул.
• отрицания могут применяться только к буквам.

Любая формула MTL эквивалентна формуле в нормальной форме. Это можно показать с помощью простой индукции по формулам. Например, формула ${ displaystyle neg ( phi { mathcal {U}} _ {S} psi)}$ эквивалентно формуле ${ Displaystyle ( neg phi { mathcal {R}} _ {S} ( neg psi)}$. Точно так же союзы и дизъюнкции можно рассматривать, используя Законы де Моргана.

Строго говоря, множество формул в положительной нормальной форме не является фрагментом MTL.

Смотрите также

• Временная пропозициональная темпоральная логика, еще одно расширение LTL, в котором можно измерить время.

Рекомендации