lógica temporal métrica

La lógica temporal métrica ( LTM ) es un caso especial de lógica temporal . Es una extensión de la lógica temporal en la que los operadores temporales se reemplazan por versiones con restricciones de tiempo, como los operadores `until` , ` next` , ` since` y ` previous` . Es una lógica de tiempo lineal que asume las abstracciones de entrelazado y de reloj ficticio. Se define sobre una semántica de tiempo entero débilmente monótona basada en puntos.

MTL se ha descrito como un formalismo de especificación prominente para sistemas en tiempo real. ^{[ 1 ]} MTL completo sobre palabras temporizadas infinitas es indecidible. ^{[ 2 ]}

Sintaxis

La lógica temporal métrica completa se define de forma similar a la lógica temporal lineal , donde se añade un conjunto de números reales no negativos a los operadores modales temporales U y S. Formalmente, la MTL se construye a partir de:

un conjunto finito de variables proposicionales AP ,
los operadores lógicos ¬ y ∨, y
el operador modal temporal $U$ $I$ (pronunciado " $φ$ hasta en $I$ $ψ$ ."), donde $I es$ un intervalo de números no negativos.
el operador modal temporal $S$ $I$ (pronunciado " $φ$ ya que en $I$ $ψ$ ."), con $I$ como se indicó anteriormente.

Cuando se omite el subíndice, es implícitamente igual a $[0,\infty )$ .

Tenga en cuenta que el siguiente operador N no se considera parte de la sintaxis MTL. En cambio, se definirá a partir de otros operadores.

Pasado y futuro

El fragmento pasado de la lógica temporal métrica , denominado past-MTL, se define como la restricción de la lógica temporal métrica completa sin el operador until . De manera similar, el fragmento futuro de la lógica temporal métrica , denominado future-MTL, se define como la restricción de la lógica temporal métrica completa sin el operador since .

Según los autores, MTL se define como el fragmento futuro de MTL, en cuyo caso MTL completo se denomina MTL+Pasado . ^{[ 1 ]}^{[ 3 ]} O MTL se define como MTL completo.

Para evitar ambigüedades, este artículo utiliza los nombres full-MTL, past-MTL y future-MTL. Cuando se cumplen las tres condiciones lógicas, simplemente se utilizará MTL.

Modelo

Dejar $T\subseteq \mathbb {R} _{+}$ representar intuitivamente un conjunto de puntos en el tiempo. $\gamma :T\to A$ una función que asocia una letra a cada momento $t\in T$ Un modelo de una fórmula MTL es una función de este tipo. $\gamma$ . Generalmente, $\gamma$ es una palabra temporizada o una señal . En esos casos, $T$ es un subconjunto discreto o un intervalo que contiene 0.

Semántica

Dejar $T$ y $\gamma$ como arriba y deja $t\in T$ un tiempo fijo. Ahora vamos a explicar qué significa una fórmula MTL $\phi$ se mantiene en el tiempo $t$ , que se denota $\gamma ,t\models \phi$ .

Dejar $I\subseteq \mathbb {R} _{+}$ y $\phi ,\psi \in MTL$ Primero consideramos la fórmula $\phi {\mathcal {U}}_{I}\psi$ Decimos que $\gamma ,t\models \phi {\mathcal {U}}_{I}\psi$ si y solo si existe algún tiempo $t'\in t+I$ de tal manera que:

$\gamma ,t'\modelos \psi$ y
para cada $t''\in T$ con $t<t''<t'$ , $\gamma ,t''\models \phi$ .

Ahora consideramos la fórmula $\phi {\mathcal {S}}_{I}\psi$ (pronunciado " $\phi$ ya que en $I$ $\psi$ .") Decimos que $\gamma ,t\models \phi {\mathcal {S}}_{I}\psi$ si y solo si existe algún tiempo $t'\in t-I$ de tal manera que:

$\gamma ,t'\models \psi$ y
para cada $t''\in T$ con $t'<t''<t$ , $\gamma ,t''\models \phi$ .

Las definiciones de $\gamma ,t\models \phi$ para los valores de $\phi$ No considerado anteriormente es similar a la definición en el caso LTL .

Operadores definidos a partir de operadores MTL básicos

Algunas fórmulas se usan con tanta frecuencia que se introduce un nuevo operador para ellas. Estos operadores generalmente no se consideran parte de la definición de MTL, sino que son azúcar sintáctico que denota fórmulas MTL más complejas. Primero consideramos operadores que también existen en LTL. En esta sección, fijamos $\phi ,\psi$ Fórmulas MTL y $I\subseteq \mathbb {R} _{+}$ .

Operadores similares a los de LTL

Liberación y regreso a

Denotamos por $\phi {\mathcal {R}}_{I}\psi$ (pronunciado " $\phi$ lanzamiento en $I$ , $\psi$ ") la fórmula $\neg (\neg \phi {\mathcal {U}}_{I}\neg \psi )$ Esta fórmula se cumple en el tiempo $t$ si alguna de las siguientes:

Hay algún tiempo $t'\in t+I$ de tal manera que $\phi$ sostiene y $\psi$ mantener en el intervalo $(t,t')\cap (t+I)$ .
en cada momento $t'\in t+I$ , $\psi$ sostiene.

El nombre "release" proviene del caso LTL, donde esta fórmula simplemente significa que $\psi$ siempre debe mantenerse, a menos que $\phi$ lo lanza.

La contraparte anterior del lanzamiento se denota por $\phi {\mathcal {B}}_{I}\psi$ (pronunciado " $\phi$ volver a en $I$ , $\psi$ ") y es igual a la fórmula $\neg (\neg \phi {\mathcal {S}}_{I}\neg \psi )$ .

Finalmente y con el tiempo

Denotamos por $\Diamond _{I}\phi$ o ${\mathcal {F}}_{I}\phi$ (pronunciado "Finalmente en $I$ , $\phi$ ", o "Finalmente en $I$ , $\phi$ ") la fórmula $\top {\mathcal {U}}_{I}\phi$ Intuitivamente, esta fórmula se cumple en el tiempo $t$ si hay algo de tiempo $t'\in t+I$ de tal manera que $\phi$ sostiene.

Denotamos por $\Box _{I}\phi$ o ${\mathcal {G}}_{I}\phi$ (pronunciado "Globalmente en $I$ , $\phi$ ",) la fórmula $\neg \Diamond _{I}\neg \phi$ Intuitivamente, esta fórmula se cumple en el tiempo $t$ si para siempre $t'\in t+I$ , $\phi$ sostiene.

Denotamos por ${\overleftarrow {\Box }}_{I}\phi$ y ${\overleftarrow {\Diamond }}_{I}\phi$ la fórmula similar a $\Box _{I}\phi$ y $\Diamond _{I}\phi$ , dónde ${\mathcal {U}}$ es reemplazado por ${\mathcal {S}}$ Ambas fórmulas tienen intuitivamente el mismo significado, pero cuando consideramos el pasado en lugar del futuro.

Siguiente y anterior

Este caso es ligeramente diferente de los anteriores, porque el significado intuitivo de las fórmulas "Siguiente" y "Anteriormente" difiere según el tipo de función. $\gamma$ consideró.

Denotamos por $\bigcirc _{I}\phi$ o ${\mathcal {N}}_{I}\phi$ (pronunciado "Siguiente en $I$ , $\phi$ ") la fórmula $\bot {\mathcal {U}}_{I}\phi$ . De manera similar, denotamos por $\ominus _{I}\phi$ ^{[ 4 ]} (pronunciado "Anteriormente en $I$ , $\phi$ ) la fórmula $\bot {\mathcal {S}}_{I}\phi$ La siguiente discusión sobre el operador Next también se aplica al operador Previously, invirtiendo el pasado y el futuro.

Cuando esta fórmula se evalúa sobre una palabra cronometrada $\gamma :T\to A$ Esta fórmula significa que ambos:

en el siguiente momento en el dominio de definición $T$ , la fórmula $\phi$ La voluntad se mantiene.
Además, la distancia entre este próximo momento y el momento actual pertenece al intervalo $I$ .
En particular, este próximo tiempo se mantiene, por lo tanto, el tiempo actual no es el final de la palabra.

Cuando esta fórmula se evalúa sobre una señal $\gamma$ , la noción de la próxima vez no tiene sentido. En cambio, "siguiente" significa "inmediatamente después". Más precisamente $\gamma ,t\models \circ \phi$ medio:

$I$ contiene un intervalo de la forma $(0,\epsilon )$ y
para cada $t'\in (t,t+\epsilon )$ , $\gamma ,t'\models \phi$ .

Otros operadores

Ahora analizaremos operadores que no se asemejan a ningún operador estándar de transporte de carga fraccionada (LTL).

Caída y ascenso

Denotamos por $\uparrow \phi$ (se pronuncia "rise" $\phi$ "), una fórmula que se cumple cuando $\phi$ se convierte en realidad. Más precisamente, o $\phi$ no se cumplía en el pasado inmediato y se cumple en este momento, o no se cumple y se cumplirá en el futuro inmediato. Formalmente $\uparrow \phi$ se define como $(\phi \land (\neg \phi {\mathcal {S}}\top ))\lor (\neg \phi \land (\phi {\mathcal {U}}\top ))$ . ^{[ 5 ]}

Con las palabras cronometradas, esta fórmula siempre se cumple. De hecho. $\phi {\mathcal {U}}\top$ y $\neg \phi {\mathcal {S}}\top$ siempre se cumple. Por lo tanto, la fórmula es equivalente a $\phi \lor \neg \phi$ , por lo tanto es cierto.

Por simetría, denotamos por $\downarrow \phi$ (pronunciado "Fall" $\phi$ ), una fórmula que se cumple cuando $\phi$ se vuelve falso. Por lo tanto, se define como $(\neg \phi \land (\phi {\mathcal {S}}\top ))\land (\phi \land (\neg \phi {\mathcal {U}}\top ))$ .

Historia y Profecía

Ahora introducimos el operador de profecía , denotado por $\triangleright$ . Lo denotamos por $\triangleright _{I}\phi$ ^{[ 6 ]} la fórmula $\neg \phi {\mathcal {U}}_{I}\phi$ Esta fórmula afirma que existe un primer momento en el futuro tal que $\phi$ se mantiene, y el tiempo para esperar este primer momento pertenece a $I$ .

Ahora consideramos esta fórmula sobre palabras temporizadas y sobre señales. Primero consideramos las palabras temporizadas. Supongamos que $I=\mid a,b\mid '$ dónde $\mid$ y $\mid '$ representa límites abiertos o cerrados. $\gamma$ una palabra cronometrada y $t$ en su dominio de definición. Sobre palabras cronometradas, la fórmula $\gamma ,t\models \triangleright _{I}\phi$ se cumple si y solo si $\gamma ,t\models \Box _{]0,b[\setminus I}\neg \phi \land \Diamond _{I}\phi$ también se cumple. Es decir, esta fórmula simplemente afirma que, en el futuro, hasta el intervalo $t+I$ se cumple, $\phi$ no debería sostenerse. Además, $\phi$ debería mantenerse en algún momento del intervalo $t+I$ De hecho, dado cualquier tiempo $t''\in t+I$ de tal manera que $\gamma ,t''\models \phi$ sostener, solo existe un número finito de tiempo $t'\in t+I$ con $t'<t''$ y $\gamma ,t'\models \phi$ Por lo tanto, necesariamente existe un valor menor de este tipo. $t''$ .

Consideremos ahora la señal. La equivalencia mencionada anteriormente ya no se cumple sobre la señal. Esto se debe a que, utilizando las variables introducidas anteriormente, puede existir un número infinito de valores correctos para $t'$ , debido a que el dominio de definición de una señal es continuo. Por lo tanto, la fórmula $\triangleright _{I}\phi$ también garantiza que el primer intervalo en el que $\phi$ Las reservas están cerradas a la izquierda.

Por simetría temporal, definimos el operador de historia , denotado por $\triangleleft$ . Definimos $\triangleleft _{I}\phi$ como $\neg \phi {\mathcal {S}}_{I}\phi$ Esta fórmula afirma que existe un último momento en el pasado tal que $\phi$ sostenido. Y el tiempo transcurrido desde ese primer momento pertenece a $I$ .

Operador no estricto

La semántica de los operadores until y since introducidos no considera el tiempo actual. Es decir, para que $\phi _{1}{\mathcal {U}}\phi _{2}$ para sostener en algún momento $t$ , ni $\phi _{1}$ ni $\phi _{2}$ tiene que sostenerse en el momento $t$ Esto no siempre es lo que se desea; por ejemplo, en la oración "no hay ningún error hasta que el sistema se apaga", en realidad puede que se desee que no haya ningún error en el momento actual. Por lo tanto, introducimos otro operador hasta , llamado hasta no estricto , denotado por ${\overline {\mathcal {U}}}$ , que tienen en cuenta la hora actual.

Denotamos por $\phi _{1}{\overline {\mathcal {U}}}_{I}\phi _{2}$ y $\phi _{1}{\overline {\mathcal {S}}}_{I}\phi _{2}$ cualquiera:

las fórmulas $\phi _{2}\lor (\phi _{1}\land (\phi _{1}{\mathcal {U}}_{I}\phi _{2}))$ y $\phi _{2}\lor (\phi _{1}\land (\phi _{1}{\mathcal {S}}_{I}\phi _{2}))$ si $0\in I$ , y
las fórmulas $\phi _{1}\land (\phi _{1}{\mathcal {U}}_{I}\phi _{2})$ y $\phi _{1}\land (\phi _{1}{\mathcal {S}}_{I}\phi _{2})$ de lo contrario.

Para cualquiera de los operadores ${\mathcal {O}}$ Como se mencionó anteriormente, denotamos ${\overline {\mathcal {O}}}$ la fórmula en la que se utilizan valores no estrictos hasta s y desde . Por ejemplo ${\overline {\Diamond }}p$ es una abreviatura de $\top {\overline {\mathcal {U}}}p$ .

El operador estricto no se puede definir usando un operador no estricto. Es decir, no hay una fórmula equivalente a $\bigcirc _{I}p$ que utiliza únicamente un operador no estricto. Esta fórmula se define como $\bot {\mathcal {U}}_{I}p$ Esta fórmula nunca puede mantenerse a la vez. $t$ si se requiere que $\bot$ se mantiene en el tiempo $t$ .

Ejemplo

A continuación, presentamos ejemplos de fórmulas MTL. Se pueden encontrar más ejemplos en el artículo sobre fragmentos de MITL, como la lógica temporal de intervalo métrico .

$\Box (p\implies \Diamond _{\{1\}}q)$ indica que cada letra $p$ es seguido exactamente una unidad de tiempo después por una carta $q$ .
$\Box (p\implies \neg \Diamond _{\{1\}}p)$ afirma que no hay dos ocurrencias sucesivas de $p$ pueden ocurrir con una diferencia de tiempo exacta entre sí.

Comparación con LTL

Una palabra infinita estándar (sin límite de tiempo) $w=a_{0},a_{1},\dots ,$ es una función de $\mathbb {N}$ a $A$ Podemos considerar dicha palabra utilizando el conjunto de tiempo $T=\mathbb {N}$ y la función $\gamma (i)=a_{i}$ . En este caso, para $\phi$ una fórmula LTL arbitraria, $w,i\models \phi$ si y solo si $\gamma ,i\models \phi$ , dónde $\phi$ se considera una fórmula MTL con operador no estricto y $[0,\infty )$ subíndice. En este sentido, MTL es una extensión de LTL.

Por esta razón, una fórmula que utiliza únicamente un operador no estricto con $[0,\infty )$ El subíndice se denomina fórmula LTL.

Complejidad algorítmica

La satisfacibilidad de ECL sobre señales es EXPSPACE - completa . ^{[ 6 ]}

Fragmentos de MTL

Ahora vamos a considerar algunos fragmentos de MTL.

MITL

Un subconjunto importante de MTL es la lógica temporal de intervalo métrico ( MITL ). Esta se define de manera similar a MTL, con la restricción de que los conjuntos $I$ , utilizado en ${\mathcal {U}}$ y ${\mathcal {S}}$ , son intervalos que no son conjuntos unitarios y cuyos límites son números naturales o infinito.

Otros subconjuntos de MITL se definen en el artículo MITL .

Fragmentos del futuro

Future-MTL ya se presentó anteriormente. Tanto sobre palabras temporizadas como sobre señales, es menos expresivo que Full-MTL ^{[ 3 ]}^{: 3} .

Lógica temporal de reloj de eventos

El fragmento Event-Clock Temporal Logic ^{[ 6 ]} de MTL, denominado EventClockTL o ECL , permite únicamente los siguientes operadores:

los operadores booleanos, y, o, no
los operadores sin límite de tiempo hasta y desde .
Los operadores de la profecía y la historia cronometradas.

En cuanto a las señales, ECL es tan expresiva como MITL y como MITL _0. La equivalencia entre estas dos últimas lógicas se explica en el artículo MITL _0. Aquí esbozamos la equivalencia de dichas lógicas con ECL.

Si $I$ no es un singleton y $\phi$ es una fórmula MITL, $\triangleright _{I}\phi$ se define como una fórmula MITL. Si $I=\{i\}$ es un singleton, entonces $\triangleright _{I}\phi$ es equivalente a $\Box _{]0,i[}\neg \phi \land \Diamond _{]0,i]}\phi$ que es una fórmula MITL. Recíprocamente, para $\psi$ una fórmula ECL y $I$ un intervalo cuyo límite inferior es 0, $\Box _{I}\psi$ es equivalente a la fórmula ECL $\neg \triangleright _{I}\neg \psi$ .

La satisfacibilidad de ECL sobre señales es PSPACE-completa . ^{[ 6 ]}

Forma normal positiva

Una fórmula MTL en forma normal positiva se define casi como cualquier fórmula MTL, con los dos cambios siguientes:

Los operadores Release y Back se introducen en el lenguaje lógico y ya no se consideran notaciones para otras fórmulas.
Las negaciones solo se pueden aplicar a las cartas.

Cualquier fórmula MTL es equivalente a una fórmula en forma normal. Esto se puede demostrar mediante una sencilla inducción sobre fórmulas. Por ejemplo, la fórmula $\neg (\phi {\mathcal {U}}_{S}\psi )$ es equivalente a la fórmula $(\neg \phi ){\mathcal {R}}_{S}(\neg \psi )$ . De manera similar, las conjunciones y disyunciones pueden considerarse utilizando las leyes de De Morgan .

En rigor, el conjunto de fórmulas en forma normal positiva no es un fragmento de MTL.

Véase también

La lógica temporal proposicional cronometrada es otra extensión de la LTL en la que se puede medir el tiempo.

Referencias

1 2 J. Ouaknine y J. Worrell, "Sobre la decidibilidad de la lógica temporal métrica", 20º Simposio Anual IEEE sobre Lógica en Ciencias de la Computación (LICS' 05), 2005, págs. 188-197.
↑ Ouaknine J., Worrell J. (2006) Sobre lógica temporal métrica y máquinas de Turing defectuosas. En: Aceto L., Ingólfsdóttir A. (eds) Fundamentos de la ciencia del software y estructuras de computación. FoSSaCS 2006. Lecture Notes in Computer Science, vol. 3921. Springer, Berlín, Heidelberg
1 2 Bouyer, Patricia ; Chevalier, Fabrice; Markey, Nicolas (2005). "Sobre la expresividad de TPTL y MTL" . En Sundar Sarukkai; Sandeep Sen (eds.). FSTTCS 2005: Fundamentos de la tecnología de software y la informática teórica, Actas . 25.ª Conferencia Internacional, Hyderabad, India, 15-18 de diciembre de 2005. Lecture Notes in Computer Science. Vol. 3821. p. 436. doi : 10.1007/11590156_35 . ISBN 978-3-540-32419-5.
↑ Maler, Oded; Nickovic, Dejan; Pnueli, Amir (2008). «Comprobación de las propiedades temporales de comportamientos discretos, temporizados y continuos». Pilares de la informática . ACM. pág. 478. ISBN 978-3-540-78126-4.
↑ Nickovic, Dejan (31 de agosto de 2009). "3" . Verificación de propiedades temporizadas e híbridas: teoría y aplicaciones (tesis).
1 2 3 4 Henzinger, TA; Raskin, JF; Schobbens, P.-Y. (1998). "Los lenguajes regulares de tiempo real". Autómatas, lenguajes y programación . Notas de clase en ciencias de la computación. Vol. 1443. pág. 590. doi : 10.1007/BFb0055086 . ISBN 978-3-540-64781-2.

[Decidabilty_Of_MITL-1] 1 2 J. Ouaknine y J. Worrell, "Sobre la decidibilidad de la lógica temporal métrica", 20º Simposio Anual IEEE sobre Lógica en Ciencias de la Computación (LICS' 05), 2005, págs. 188-197.

[MTL_and_Faulty_Turing_Machine-2] Ouaknine J., Worrell J. (2006) Sobre lógica temporal métrica y máquinas de Turing defectuosas. En: Aceto L., Ingólfsdóttir A. (eds) Fundamentos de la ciencia del software y estructuras de computación. FoSSaCS 2006. Lecture Notes in Computer Science, vol. 3921. Springer, Berlín, Heidelberg

[ExpressivenesOfTPTLAndMtl-3] 1 2 Bouyer, Patricia ; Chevalier, Fabrice; Markey, Nicolas (2005). "Sobre la expresividad de TPTL y MTL" . En Sundar Sarukkai; Sandeep Sen (eds.). FSTTCS 2005: Fundamentos de la tecnología de software y la informática teórica, Actas . 25.ª Conferencia Internacional, Hyderabad, India, 15-18 de diciembre de 2005. Lecture Notes in Computer Science. Vol. 3821. p. 436. doi : 10.1007/11590156_35 . ISBN 978-3-540-32419-5.

[LTLPlusPast-4] Maler, Oded; Nickovic, Dejan; Pnueli, Amir (2008). «Comprobación de las propiedades temporales de comportamientos discretos, temporizados y continuos». Pilares de la informática . ACM. pág. 478. ISBN 978-3-540-78126-4.

[Checking_Timed_and_Hybrid_Properties-5] Nickovic, Dejan (31 de agosto de 2009). "3" . Verificación de propiedades temporizadas e híbridas: teoría y aplicaciones (tesis).

[RegularRealTime-6] 1 2 3 4 Henzinger, TA; Raskin, JF; Schobbens, P.-Y. (1998). "Los lenguajes regulares de tiempo real". Autómatas, lenguajes y programación . Notas de clase en ciencias de la computación. Vol. 1443. pág. 590. doi : 10.1007/BFb0055086 . ISBN 978-3-540-64781-2.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]