Lógica temporal lineal

En lógica , la lógica temporal lineal ( LTL ) es una lógica temporal modal con modalidades que se refieren al tiempo. En LTL, se pueden codificar fórmulas sobre el futuro de una ruta infinita en un sistema de transiciones, por ejemplo, una condición terminará siendo verdadera, una condición será verdadera hasta que otra se vuelva verdadera, etc. Esta lógica es más débil que la lógica CTL * , que permite que las condiciones se expresen en ramificaciones de rutas y no solo en una sola ruta. LTL también se denomina a veces lógica proposicional temporal , abreviado LTP ( PTL English). La lógica temporal lineal (LTL) es un fragmento de S1S (para segundo orden con 1 sucesor), lógica monádica de segundo orden con un sucesor.

LTL fue propuesto por primera vez para la verificación formal de programas de computadora por Amir Pnueli en 1977.

Sintaxis

LTL se construye a partir de un conjunto finito de variables proposicionales AP , operadores lógicos ¬ y ∨ y operadores temporales modal X (algunas notaciones utilizan O o N ) y U . Formalmente, el conjunto de fórmulas de LTL en AP se define inductivamente de la siguiente manera:

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

X se lee como siguiente ( ne x t en inglés) y U se lee como hasta ( u ntil en inglés). Podemos agregar otros operadores, no necesarios pero que simplifican la escritura de ciertas fórmulas.

Por ejemplo, generalmente se agregan los operadores lógicos ∧, →, ↔, verdadero y falso. Los operadores temporales a continuación también son:

G siempre ( g verall ( g lobally Inglés));
F finalmente (en el f UTUR ( en el f uture Inglés));
R de liberación ( r elease en inglés);
W para el débil hasta ( w EAK hasta en Inglés).

Semántica

Una fórmula LTL puede satisfacerse mediante una serie infinita de evaluaciones de verdad de las variables en AP . Sea w = a 0 , a 1 , a 2 , ... tal palabra-mot. Sea w (i) = a i . Sea w i = 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: ${\ Displaystyle \ vDash}$

w p si p ∈ w (0) ${\ Displaystyle \ vDash}$
w ¬ψ si w ψ ${\ Displaystyle \ vDash}$ ${\ Displaystyle \ nvDash}$
w φ ∨ ψ si w φ o w ψ ${\ Displaystyle \ vDash}$ ${\ Displaystyle \ vDash}$ ${\ Displaystyle \ vDash}$
w X ψ si w 1 ψ (ψ debe ser verdadero en el siguiente paso ) ${\ Displaystyle \ vDash}$ ${\ Displaystyle \ vDash}$
w φ U ψ si existe i ≥ 0 tal que w i ψ y para todo 0 ≤ k <i, w k φ (φ debe permanecer verdadero hasta que ψ se convierta en verdadero) ${\ Displaystyle \ vDash}$ ${\ Displaystyle \ vDash}$ ${\ Displaystyle \ vDash}$

Decimos que una palabra-ω w satisface una fórmula LTL ψ cuando w ψ. ${\ Displaystyle \ vDash}$

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

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

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

φ R ψ ≡ ¬ (¬φ U ¬ψ)
F ψ ≡ verdadero U ψ (ψ eventualmente se convierte en cierto)
G ψ ≡ falso R ψ ≡ ¬ F ¬ψ (ψ siempre permanece verdadero)

La semántica de los operadores temporales se puede representar de la siguiente manera:

Operador	Símbolo alternativo	Explicación
Operadores unarios :
X $\ phi$	${\ Displaystyle \ bigcirc \ phi}$	siguiente: debe satisfacerse en el siguiente estado. $\ phi$
GRAMO $\ phi$	${\ Displaystyle \ Box \ phi}$	G verall: debe cumplirse en todos los estados futuros. $\ phi$
F $\ phi$	${\ Displaystyle \ Diamond \ phi}$	F inalmente: debe ser satisfecha en un estado futuro. $\ phi$
Operadores binarios :
$\ psi$ U $\ phi$	${\ Displaystyle \ psi \; {\ mathcal {U}} \, \ phi}$	Hasta: debe estar satisfecho en todos los estados hasta un estado o está satisfecho, no incluido. $\ psi$ $\ phi$
$\ psi$ R $\ phi$	${\ Displaystyle \ psi \; {\ mathcal {R}} \, \ phi}$	R o lograr: estar satisfecho en todos los estados como no está satisfecho. $\ phi$ $\ psi$ Si nunca está satisfecho, debe ser verdad en todas partes. $\ psi$ $\ phi$

Equivalencias

Sean Φ, ψ y ρ fórmulas LTL. Las siguientes tablas muestran equivalencias útiles.

Distributividad
X (Φ ∨ ψ) ≡ ( X Φ) ∨ ( X ψ)	X (Φ ∧ ψ) ≡ ( X Φ) ∧ ( X ψ)	X (Φ U ψ) ≡ ( X Φ) U ( X ψ)
F (Φ ∨ ψ) ≡ ( F Φ) ∨ ( F ψ)	G (Φ ∧ ψ) ≡ ( G Φ) ∧ ( G ψ)
ρ U (Φ ∨ ψ) ≡ (ρ U Φ) ∨ (ρ U ψ)	(Φ ∧ ψ) U ρ ≡ (Φ U ρ) ∧ (ψ U ρ)

Negación
¬ X Φ ≡ X ¬Φ	¬ G Φ ≡ F ¬Φ	¬ F Φ ≡ G ¬Φ
¬ (Φ U ψ) ≡ (¬Φ R ¬ψ)	¬ (Φ R ψ) ≡ (¬Φ U ¬ψ)

Propiedades temporales especiales
F Φ ≡ F F Φ	G Φ ≡ G G Φ	Φ U ψ ≡ Φ U (Φ U ψ)
Φ U ψ ≡ ψ ∨ (Φ ∧ X (Φ U ψ))	Φ W ψ ≡ ψ ∨ (Φ ∧ X (Φ W ψ))	Φ R ψ ≡ ψ ∧ (Φ ∨ X (Φ R ψ))
G Φ ≡ Φ ∧ X ( G Φ)	F Φ ≡ Φ ∨ X ( F Φ)

Forma normal negativa

Todas las fórmulas LTL se pueden transformar en forma normal negativa , donde

todas las negaciones aparecen solo frente a proposiciones atómicas,
sólo pueden aparecer los operadores lógicos verdadero , falso , ∧ y ∨, y
sólo pueden aparecer los operadores lógicos X , U y R.

Autómatas Büchi

Cualquier fórmula LTL es equivalente a un autómata Büchi de tamaño como máximo exponencial en el tamaño de la fórmula. Para LTL sobre trazas finitas, llamadas LTLf, cualquier fórmula es equivalente a un autómata finito no determinista de tamaño como máximo exponencial en el tamaño de la fórmula.

Problemas algorítmicos

La verificación del modelo y el problema de satisfacibilidad es PSPACE completo. La síntesis LTL y el problema de verificar un juego con un objetivo LTL es 2EXPTIME-complete.

Aprendizaje reforzado

Los objetivos de los agentes a veces se escriben en LTL, tanto para los modelos como para los enfoques sin modelo.

Extensiones

Cuantización de segundo orden

En el capítulo 3 de su tesis, Sistla amplía LTL agregando cuantificaciones de segundo orden. En ese momento, LTL se llamaba más bien PTL (para lógica temporal proposicional ). Esta extensión se llama QPTL ( lógica temporal proposicional cuantificada ). Por ejemplo, hay una fórmula de QPTL que dice "hay una manera de dar valores a la proposición p en toda la línea de tiempo, por ejemplo, independientemente de cómo asignar valores a la proposición q en toda la línea de tiempo, siempre tenemos que p es equivalente al hecho de que mañana q ". Sistla, en el capítulo 3 de su tesis, demuestra que decidir si una fórmula en forma de apéndice y con una sola alternancia de QPTL es verdadera es EXPSPACE-completo. ${\ Displaystyle \ existe p, \ forall q, G (p \ leftrightarrow Xq)}$

Como mencionan Sistla et al., Se puede reducir S1S que no es elemental para QPTL. Por tanto, la veracidad de una fórmula QPTL no es elemental. Más específicamente, Sistla et al. demuestre que el problema de veracidad de QPTL restringido a fórmulas con k alternancias es kNEXPSPACE-completo.

Ver también

Notas y referencias

Notas

Estos símbolos se utilizan a veces en la literatura para designar estos operadores.

Referencias

(fr) Este artículo está tomado parcial o totalmente del artículo de Wikipedia en inglés titulado “ Lógica temporal lineal ” ( ver la lista de autores ) .

Lógica en Ciencias de la Computación: Modelado y Razonamiento de Sistemas: página 175
Lógica temporal de tiempo lineal
(en) Dov M. Gabbay , A. Kurucz, F. Wolter, Mr. Zakharyaschev, Lógicas modales multidimensionales: teoría y aplicaciones , Amsterdam / Boston, Elsevier ,2003( ISBN 978-0-444-50826-3 , leer en línea ) , pág. 46
Amir Pnueli , La lógica temporal de los programas.
Sec. 5.1 de Christel Baier y Joost-Pieter Katoen, Principles of Model Checking, MIT Press [1]
Christel Baier y Joost-Pieter Katoen , Principios de verificación de modelos (serie de representación y mente) , The MIT Press ,31 de mayo de 2008, 975 p. ( ISBN 978-0-262-02649-9 y 0-262-02649-X , lea en línea )
Giuseppe De Giacomo y Moshe Y. Vardi , " Síntesis de LTL y LDL en trazas finitas ", IJCAI , AAAI Press,25 de julio de 2015, p. 1558-1564 ( ISBN 9781577357384 , leído en línea , consultado el 7 de febrero de 2018 )
(en) A. Pnueli y R. Rosner, " Sobre la síntesis de una unidad reactiva " , 16º Simposio ACM es SIGPLAN-SIGACT Principios de lenguajes de programación (conferencia) ,1989( leer en línea , consultado el 7 de noviembre de 2019 )
Jie Fu y Ufuk Topcu , " Probablemente el aprendizaje y el control de MDP aproximadamente correctos con restricciones de lógica temporal ", arXiv: 1404.7073 [cs] ,28 de abril de 2014( leer en línea , consultado el 5 de diciembre de 2019 )
D. Sadigh , ES Kim , S. Coogan y SS Sastry , " Un enfoque basado en el aprendizaje para controlar la síntesis de los procesos de decisión de Markov para especificaciones lógicas temporales lineales ", 53ª Conferencia IEEE sobre Decisión y Control ,diciembre de 2014, p. 1091-1096 ( DOI 10.1109 / CDC.2014.7039527 , leído en línea , consultado el 5 de diciembre de 2019 )
(in) Giuseppe De Giacomo Luca Iocchi Marco Favorito y Fabio Patrizi , " Fundamentos para tornillos de restricción: aprendizaje de refuerzo con especificaciones de restricción LTLf / LdlF " , Actas de la Conferencia internacional sobre planificación y programación automatizadas , vol. 29,6 de julio de 2019, p. 128-136 ( ISSN 2334-0843 , leído en línea , consultado el 5 de diciembre de 2019 )
Mohammadhosein Hasanbeig , Alessandro Abate y Daniel Kroening , " Q-iteración ajustada neuronal con restricciones lógicas ", Actas de la 18a Conferencia Internacional sobre Agentes Autónomos y Sistemas de Agentes Múltiples , Fundación Internacional para Agentes Autónomos y Sistemas de Agentes Múltiples, aAMAS '19,2019, p. 2012-2014 ( ISBN 978-1-4503-6309-9 , leído en línea , consultado el 5 de diciembre de 2019 )
Rodrigo Toro Icarte , Toryn Q. Klassen , Richard Valenzano y Sheila A. McIlraith , " Enseñar múltiples tareas a un agente de RL usando LTL ", Actas de la 17a Conferencia Internacional sobre Agentes Autónomos y Sistemas de Agentes Múltiples , Fundación Internacional para Agentes Autónomos y Multiagente Sistemas, aAMAS '18,2018, p. 452–461 ( leído en línea , consultado el 5 de diciembre de 2019 )
“ Aspectos teóricos en el diseño y verificación de sistemas distribuidos | Guide books ” , en dl.acm.org ( DOI 10.5555 / 911361 , consultado el 7 de febrero de 2020 )
(en) A. Prasad Sistla , Moshe Y. Vardi y Pierre Wolper , " El problema de complementación de los autómatas Büchi con aplicaciones a la lógica temporal " , Informática teórica , vol. 49, n o 21 st de enero de 1 987, p. 217–237 ( ISSN 0304-3975 , DOI 10.1016 / 0304-3975 (87) 90008-9 , leído en línea , consultado el 7 de febrero de 2020 )
" LA TEORÍA DEL SUCESOR DE SEGUNDO ORDEN MONADICO DÉBIL NO ES ELEMENTAL-RECURSIVO | Guide books ” , en dl.acm.org ( DOI 10.5555 / 889571 , consultado el 7 de febrero de 2020 )

enlaces externos