Lógica temporal lineal

En lógica , la lógica temporal lineal o lógica temporal de tiempo lineal ^[1]^[2] ( LTL ) es una lógica temporal modal con modalidades referidas al tiempo. En LTL, se pueden codificar fórmulas sobre el futuro de las rutas , por ejemplo, una condición eventualmente será verdadera, una condición será verdadera hasta que otro hecho se vuelva verdadero, etc. Es un fragmento del CTL* más complejo , que además permite la ramificación. tiempo y cuantificadores . LTL a veces se denomina lógica temporal proposicional , abreviada PTL . ^[3] En términos de poder expresivo , la lógica temporal lineal (LTL) es un fragmento de la lógica de primer orden . ^[4]^[5]

LTL fue propuesto por primera vez para la verificación formal de programas informáticos por Amir Pnueli en 1977. ^[6]

Sintaxis

LTL se construye a partir de un conjunto finito de variables proposicionales AP , los operadores lógicos ¬ y ∨, y los operadores modales temporales X (alguna literatura usa O o N ) y U. Formalmente, el conjunto de fórmulas LTL sobre AP se define inductivamente de la siguiente manera:

si p ∈ AP entonces p es una fórmula LTL;
si ψ y φ son fórmulas LTL, entonces ¬ψ, φ ∨ ψ, X ψ y φ U ψ son fórmulas LTL. ^[7]

X se lee como siguiente y U se lee como hasta . Además de estos operadores fundamentales, existen operadores lógicos y temporales adicionales definidos en términos de operadores fundamentales, para poder escribir fórmulas LTL de manera sucinta. Los operadores lógicos adicionales son ∧, →, ↔, verdadero y falso . A continuación se muestran los operadores temporales adicionales.

G para siempre ( g globalmente)
F de finalmente
R para liberar
W para débil hasta
M para liberación poderosa

Semántica

Una fórmula LTL puede satisfacerse mediante una secuencia infinita de valoraciones de verdad de variables en AP . Estas secuencias pueden verse como una palabra en un camino de una estructura de Kripke (una palabra ω sobre el alfabeto 2 ^AP ). Sea w = a ₀ ,a ₁ ,a ₂ ,... una palabra ω. Sea w ( i ) = ai _. Sea w ⁱ = a _i , a _{i +1} ,..., que es un sufijo de w . Formalmente, la relación de satisfacción ⊨ entre una palabra y una fórmula LTL se define de la siguiente manera:

w ⊨ p si p ∈ w (0)
w ⊨ ¬ ψ si w ⊭ ψ
w ⊨ φ ∨ ψ si w ⊨ φ o w ⊨ ψ
w ⊨ X ψ si w ¹ ⊨ ψ (en el siguiente paso de tiempo ψ debe ser verdadero)
w ⊨ φ U ψ si existe i ≥ 0 tal que w ⁱ ⊨ ψ y para todo 0 ≤ k < i, w ^k ⊨ φ ( φ debe permanecer verdadero hasta que ψ se vuelva verdadero)

Decimos que una palabra ω w satisface una fórmula LTL ψ cuando w ⊨ ψ . El lenguaje ω L ( ψ ) definido por ψ es { w | w ⊨ ψ }, que es el conjunto de ω-palabras que satisfacen ψ . Una fórmula ψ es satisfactoria si existe una palabra ω w tal que w ⊨ ψ . Una fórmula ψ es válida si para cada palabra ω w sobre el alfabeto 2 ^AP , tenemos w ⊨ ψ .

Los operadores lógicos adicionales se definen de la siguiente manera:

φ ∧ ψ ≡ ¬(¬ φ ∨ ¬ ψ )
φ → ψ ≡ ¬ φ ∨ ψ
φ ↔ ψ ≡ ( φ → ψ ) ∧ ( ψ → φ )
verdadero ≡ p ∨ ¬ p , donde p ∈ AP
falso ≡ ¬ verdadero

Los operadores temporales adicionales R , F y G se definen de la siguiente manera:

ψ R φ ≡ ¬(¬ ψ U ¬ φ ) ( φ permanece verdadero hasta e incluyendo una vez que ψ se vuelve verdadero. Si ψ nunca se vuelve verdadero, φ debe permanecer verdadero para siempre. ψ libera φ .)
F ψ ≡ verdadero U ψ (eventualmente ψ se vuelve verdadero)
G ψ ≡ falso R ψ ≡ ¬ F ¬ ψ ( ψ siempre permanece verdadero)

Débil hasta y liberación fuerte.

Algunos autores también definen un operador binario débil hasta , denotado W , con una semántica similar a la del operador hasta, pero no es necesario que ocurra la condición de parada (similar a la liberación). ^[8] A veces es útil ya que tanto U como R pueden definirse en términos de los débiles hasta que:

ψ W φ ≡ ( ψ U φ ) ∨ GRAMO ψ ≡ ψ U ( φ ∨ GRAMO ψ ) ≡ φ R ( φ ∨ ψ )
ψ U φ ≡ F φ ∧ ( ψ W φ )
ψ R φ ≡ φ W ( φ ∧ ψ )

El operador binario de liberación fuerte , denominado M , es el dual de débil hasta. Se define de manera similar al operador hasta, de modo que la condición de liberación debe cumplirse en algún momento. Por tanto, es más fuerte que el operador de liberación.

ψ M φ ≡ ¬(¬ ψ W ¬ φ ) ≡ ( ψ R φ ) ∧ F ψ ≡ ψ R ( φ ∧ F ψ ) ≡ φ U ( ψ ∧ φ )

La semántica de los operadores temporales se presenta gráficamente de la siguiente manera.

Equivalencias

Sean φ, ψ y ρ fórmulas LTL. Las siguientes tablas enumeran algunas de las equivalencias útiles que amplían las equivalencias estándar entre los operadores lógicos habituales.

Negación forma normal

Todas las fórmulas de LTL se pueden transformar en forma normal de negación , donde

todas las negaciones aparecen sólo delante de las proposiciones atómicas,
sólo pueden aparecer otros operadores lógicos verdadero , falso , ∧ y ∨, y
sólo pueden aparecer los operadores temporales X , U y R.

Utilizando las equivalencias anteriores para la propagación de la negación, es posible derivar la forma normal. Esta forma normal permite que R , verdadero , falso y ∧ aparezcan en la fórmula, que no son operadores fundamentales de LTL. Tenga en cuenta que la transformación a la forma normal de negación no aumenta la longitud de la fórmula. Esta forma normal es útil en la traducción de una fórmula LTL a un autómata Büchi .

Relaciones con otras lógicas

Se puede demostrar que LTL es equivalente a la lógica monádica de orden de primer orden , FO[<]—un resultado conocido como teorema de Kamp— ^[9] o equivalentemente a lenguajes sin estrellas . ^[10]

La lógica de árbol de cálculo (CTL) y la lógica temporal lineal (LTL) son un subconjunto de CTL* , pero son incomparables. Por ejemplo,

Ninguna fórmula en CTL puede definir el lenguaje definido por la fórmula LTL F ( G p).
Ninguna fórmula en LTL puede definir el lenguaje definido por las fórmulas CTL AG (p → ( EX q ∧ EX ¬q)) o AG ( EF (p)).

Problemas computacionales

La verificación del modelo y la satisfacibilidad frente a una fórmula LTL son problemas completos de PSPACE . La síntesis LTL y el problema de verificación de juegos contra una condición ganadora LTL es 2EXPTIME-completo . ^[11]

Aplicaciones

Verificación del modelo lógico temporal lineal teórico de autómatas: Una forma importante de verificar el modelo es expresar las propiedades deseadas (como las descritas anteriormente) utilizando operadores LTL y verificar si el modelo satisface esta propiedad. Una técnica es obtener un autómata Büchi que sea equivalente al modelo (acepta una palabra ω precisamente si es el modelo) y otra que sea equivalente a la negación de la propiedad (acepta una palabra ω precisamente si satisface la condición negada). propiedad) (cf. lógica temporal lineal para el autómata Büchi ). La intersección de los dos autómatas de Büchi no deterministas está vacía si y sólo si el modelo satisface la propiedad. ^[12]

Expresar propiedades importantes en la verificación formal.: Hay dos tipos principales de propiedades que se pueden expresar usando lógica temporal lineal: las propiedades de seguridad generalmente indican que algo malo nunca sucede ( G ¬ ϕ ), mientras que las propiedades de vida establecen que algo bueno sigue sucediendo ( GF ψ o G ( ϕ → F ψ )). ^[13] De manera más general, las propiedades de seguridad son aquellas para las cuales cada contraejemplo tiene un prefijo finito tal que, sin importar cómo se extienda a un camino infinito, sigue siendo un contraejemplo. Para las propiedades de vida, por otro lado, cada camino finito se puede extender a un camino infinito que satisfaga la fórmula.

Idioma de especificación: Una de las aplicaciones de la lógica temporal lineal es la especificación de preferencias en el lenguaje de definición de dominio de planificación con el fin de realizar una planificación basada en preferencias . ^{[ cita necesaria ]}

Extensiones

La lógica temporal lineal paramétrica extiende LTL con variables en la modalidad hasta. ^[14]

Ver también

Wikimedia Commons tiene medios relacionados con la lógica temporal lineal .

Referencias

^ Lógica en informática: modelado y razonamiento sobre sistemas: página 175
^ "Lógica temporal en tiempo lineal". Archivado desde el original el 30 de abril de 2017 . Consultado el 19 de marzo de 2012 .
^ Dov M. Gabbay ; A. Kurucz; F. Wolter; M. Zakharyaschev (2003). Lógicas modales multidimensionales: teoría y aplicaciones. Elsevier. pag. 46.ISBN 978-0-444-50826-3.
^ Diekert, Volker. "Idiomas definibles de primer orden" (PDF) . Universidad de Stuttgart.
^ Kamp, Hans (1968). Lógica tensa y teoría del orden lineal (Doctor). Universidad de California, Los Angeles.
↑ Amir Pnueli , La lógica temporal de los programas. Actas del 18º Simposio Anual sobre Fundamentos de la Informática (FOCS) , 1977, 46–57. doi :10.1109/SFCS.1977.32
^ Segundo. 5.1 de Christel Baier y Joost-Pieter Katoen , Principios de verificación de modelos , MIT Press "Principios de verificación de modelos - MIT Press". Archivado desde el original el 4 de diciembre de 2010 . Consultado el 17 de mayo de 2011 .
^ Segundo. 5.1.5 "Hasta débil, liberación y forma normal positiva" de los principios de verificación de modelos.
^ Abramsky, Sansón ; Gavoille, Cyril; Kirchner, Claude; Spirakis, Paul (30 de junio de 2010). Autómatas, Lenguajes y Programación: 37º Coloquio Internacional, ICALP... - Google Books. ISBN 9783642141614. Consultado el 30 de julio de 2014 .
^ Moshe Y. Vardi (2008). "De la Iglesia y antes del PSL ". En Orna Grumberg ; Helmut Veith (eds.). 25 años de verificación de modelos: historia, logros, perspectivas . Saltador. ISBN 978-3-540-69849-4.preimpresión
^ A. Pnueli y R. Rosner. "Sobre la síntesis de un módulo reactivo" En Actas del 16º Simposio ACM SIGPLAN-SIGACT sobre principios de lenguajes de programación (POPL '89). Association for Computing Machinery, Nueva York, NY, EE. UU., 179–190. https://doi.org/10.1145/75277.75293
^ Moshe Y. Vardi. Un enfoque teórico de autómatas de la lógica temporal lineal. Actas del octavo taller de orden superior de Banff (Banff'94). Apuntes de conferencias sobre informática , vol. 1043, págs. 238–266, Springer-Verlag, 1996. ISBN 3-540-60915-6 .
^ Bowen Alpern, Fred B. Schneider , Definición de vida , Cartas sobre procesamiento de información , volumen 21, número 4, 1985, páginas 181-185, ISSN 0020-0190, https://doi.org/10.1016/0020-0190(85) 90056-0
^ Chakraborty, Souymodip; Katoen, Joost-Pieter (2014). Díaz, Josep; Lanese, Iván; Sangiorgi, Davide (eds.). "LTL paramétrico en cadenas de Markov". Informática Teórica . Apuntes de conferencias sobre informática. 7908 . Springer Berlín Heidelberg: 207–221. arXiv : 1406.6683 . Código Bib : 2014arXiv1406.6683C. doi :10.1007/978-3-662-44602-7_17. ISBN 978-3-662-44602-7. S2CID 12538495.

enlaces externos

Una presentación de LTL
Lógica temporal de tiempo lineal y autómatas Büchi
LTL Diapositivas didácticas del profesor Alessandro Artale en la Universidad Libre de Bozen-Bolzano
Algoritmos de traducción de LTL a Buchi una genealogía, del sitio web de Spot una biblioteca para la verificación de modelos.