Lineær tidsmæssig logik

I logik er lineær temporal logik ( LTL ) modal tidsmæssig logik med modaliteter, der henviser til tid. I LTL kan man kode formler om fremtiden for en uendelig sti i et system med overgange, for eksempel vil en tilstand ende med at være sand, en betingelse vil være sand, indtil en anden bliver sand osv. Denne logik er svagere end CTL * -logik , som gør det muligt at udtrykke betingelser på forgreninger af stier og ikke kun på en enkelt sti. LTL kaldes også undertiden temporal propositional logic , forkortet LTP ( PTL English). Lineær tidsmæssig logik (LTL) er et fragment af S1S (for andenordens med 1 efterfølger), monadisk andenordenslogik med en efterfølger.

LTL blev først foreslået til den formelle verifikation af computerprogrammer af Amir Pnueli i 1977.

Syntaks

LTL er konstrueret af et endeligt sæt propositional variabler AP , logiske operatorer ¬ og ∨ og tidsmæssige operatører modal X (nogle notationer bruger O eller N ) og U . Formelt er sættet med formler af LTL på AP induktivt defineret som følger:

hvis p ∈ AP så er p en formel for LTL;
hvis ψ og φ er LTL-formler, så er ¬ψ, φ ∨ ψ, X ψ og φ U ψ LTL-formler.

X læses som næste ( ne x t på engelsk) og U læses som op til ( u ntil på engelsk). Vi kan tilføje andre operatorer, ikke nødvendige, men som forenkler skrivningen af visse formler.

For eksempel tilføjes normalt de logiske operatorer ∧, →, ↔, true og false. De tidsmæssige operatører nedenfor er også:

G for evigt ( g verall ( g lobalt engelsk));
F endelig (i f utur ( i f OMMENDE engelsk));
R til frigivelse ( r Elease engelsk);
W for svag indtil ( w EAK indtil på engelsk).

Semantik

En LTL-formel kan opfyldes ved en uendelig række sandhedsevalueringer af variablerne i AP . Lad w = a 0 , a 1 , a 2 , ... sådan et ord-mot. Lad w (i) = a i . Lad w i = a i , a i + 1 , ..., som er et suffiks af w . Formelt defineres tilfredshedsforholdet mellem et ord og en LTL-formel som følger: ${\ displaystyle \ vDash}$

w p hvis p ∈ w (0) ${\ displaystyle \ vDash}$
w ¬ψ hvis w ψ ${\ displaystyle \ vDash}$ ${\ displaystyle \ nvDash}$
w φ ∨ ψ hvis w φ eller w ψ ${\ displaystyle \ vDash}$ ${\ displaystyle \ vDash}$ ${\ displaystyle \ vDash}$
w X ψ hvis w 1 ψ (ψ skal være sandt i næste trin ) ${\ displaystyle \ vDash}$ ${\ displaystyle \ vDash}$
w φ U ψ hvis der findes i ≥ 0 sådan at w i ψ og for alle 0 ≤ k <i, w k φ (φ skal forblive sand, indtil ψ bliver sand) ${\ displaystyle \ vDash}$ ${\ displaystyle \ vDash}$ ${\ displaystyle \ vDash}$

Vi siger, at et ord-ω w opfylder en LTL-formel ψ når w ψ. ${\ displaystyle \ vDash}$

Yderligere logiske operatorer defineres som følger:

φ ∧ ψ ≡ ¬ (¬φ ∨ ¬ψ)
φ → ψ ≡ ¬φ ∨ ψ
φ ↔ ψ ≡ (φ → ψ) ∧ (ψ → φ)
sand ≡ p ∨ ¬p, hvor p ∈ AP
falsk ≡ ¬ sandt

De ekstra tidsoperatører R , F og G er defineret som følger:

φ R ψ ≡ ¬ (¬φ U ¬ψ)
F ψ ≡ sand U ψ (ψ bliver til sidst sand)
G ψ ≡ falsk R ψ ≡ ¬ F ¬ψ (ψ forbliver altid sand)

Semantikken for tidsmæssige operatorer kan repræsenteres som følger:

Operatør	Alternativt symbol	Forklaring
Unary operatører :
x $\ phi$	${\ displaystyle \ bigcirc \ phi}$	næste: skal opfyldes i den næste tilstand. $\ phi$
G $\ phi$	${\ displaystyle \ Box \ phi}$	G Overordnet forventes: skal være opfyldt i alle fremtidige tilstande. $\ phi$
F $\ phi$	${\ displaystyle \ Diamond \ phi}$	F inally: skal være tilfreds i en fremtidig tilstand. $\ phi$
Binære operatører :
$\ psi$ U $\ phi$	${\ displaystyle \ psi \; {\ mathcal {U}} \, \ phi}$	Indtil: skal opfyldes i alle stater op til en stat eller er tilfreds, ikke inkluderet. $\ psi$ $\ phi$
$\ psi$ R $\ phi$	${\ displaystyle \ psi \; {\ mathcal {R}} \, \ phi}$	R o opnå: at være opfyldt i alle stater, som ikke er opfyldt. $\ phi$ $\ psi$ Hvis er aldrig tilfreds, skal være sandt overalt. $\ psi$ $\ phi$

Ækvivalenser

Lad Φ, ψ og ρ være LTL-formler. Følgende tabeller viser nyttige ækvivalenser.

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

Negation
¬ X Φ ≡ X ¬Φ	¬ G Φ ≡ F ¬Φ	¬ F Φ ≡ G ¬Φ
¬ (Φ U ψ) ≡ (¬Φ R ¬ψ)	¬ (Φ R ψ) ≡ (¬Φ U ¬ψ)

Særlige tidsmæssige egenskaber
F Φ ≡ F F Φ	G Φ ≡ G G Φ	Φ U ψ ≡ Φ U (Φ U ψ)
Φ U ψ ≡ ψ ∨ (Φ ∧ X (Φ U ψ))	Φ W ψ ≡ ψ ∨ (Φ ∧ X (Φ W ψ))	Φ R ψ ≡ ψ ∧ (Φ ∨ X (Φ R ψ))
G Φ ≡ Φ ∧ X ( G Φ)	F Φ ≡ Φ ∨ X ( F Φ)

Negativ normal form

Alle LTL-formler kan omdannes til negativ normal form , hvor

alle negationer vises kun foran atomiske propositioner,
kun de logiske operatorer true , false , ∧ og ∨ kan vises, og
kun de logiske operatorer X , U og R kan vises.

Büchi automata

Enhver LTL-formel svarer til en Büchi-automat med størrelse, der er mest eksponentiel i formlenes størrelse. For LTL over endelige spor, kaldet LTLf, svarer enhver formel til en ikke-deterministisk endelig automat med størrelse, der mest eksponentiel i størrelsen af formlen.

Algoritmiske problemer

Modelkontrol og tilfredsstillelsesproblemet er PSPACE-komplet. LTL-syntese og problemet med at verificere et spil med et LTL-mål er 2EXPTIME-komplet.

Forstærkning læring

Agentmål skrives undertiden i LTL til både modeller og ikke-modeltilgange.

Udvidelser

Anden ordens kvantisering

I kapitel 3 i sin afhandling udvider Sistla LTL ved at tilføje kvantificeringer af anden orden. På det tidspunkt blev LTL kaldet temmelig PTL (for propositionel tidsmæssig logik ). Denne udvidelse kaldes QPTL ( kvantificeret propositionel tidsmæssig logik ). For eksempel er en formel fra QPTL, der læser "der er en måde at give værdier til propositionen p over hele tidslinjen, såsom uanset hvordan man tildeler værdier til propositionen q over hele tidslinjen, har vi altid at p svarer til det faktum, at i morgen q ". Sistla, i kapitel 3 i sin afhandling, demonstrerer, at det er EXPSPACE-komplet at beslutte, om en formel i appendiksform og med en enkelt alternering af QPTL er sand. ${\ displaystyle \ findes p, \ forall q, G (p \ leftrightarrow Xq)}$

Som nævnt af Sistla et al., Kan man reducere S1S, som ikke er elementær i forhold til QPTL. Sandheden af en QPTL-formel er derfor ikke-elementær. Mere specifikt Sistla et al. viser, at QPTL-sandhedsproblemet begrænset til formler med k-alternationer er kNEXPSPACE-komplet.

Se også

Noter og referencer

Bemærkninger

Disse symboler bruges undertiden i litteraturen til at betegne disse operatører.

Referencer

(fr) Denne artikel er helt eller delvist taget fra Wikipedia-artiklen på engelsk med titlen " Lineær tidsmæssig logik " ( se listen over forfattere ) .

Logik inden for datalogi: Modellering og begrundelse for systemer: side 175
Temporal logik med lineær tid
(in) Dov M. Gabbay , A. Kurucz, F. Wolter, Mr. Zakharyaschev, Mangedimensionel modal logik: teori og anvendelser , Amsterdam / Boston, Elsevier ,2003( ISBN 978-0-444-50826-3 , læs online ) , s. 46
Amir Pnueli , programmernes tidsmæssige logik.
Sek. 5.1 af Christel Baier og Joost-Pieter Katoen, principper for modelkontrol, MIT Press [1]
Christel Baier og Joost-Pieter Katoen , principper for modelkontrol (repræsentation og sindsserie) , The MIT Press ,31. maj 2008, 975 s. ( ISBN 978-0-262-02649-9 og 0-262-02649-X , læs online )
Giuseppe De Giacomo og Moshe Y. Vardi , " Syntese for LTL og LDL om endelige spor ", IJCAI , AAAI Press,25. juli 2015, s. 1558–1564 ( ISBN 9781577357384 , læst online , adgang til 7. februar 2018 )
(in) A. Pnueli og R. Rosner, " Om syntesen af en reaktiv enhed " , 16. ACM Symposium er SIGPLAN-SIGACT Principper for programmeringssprog (konference) ,1989( læs online , konsulteret den 7. november 2019 )
Jie Fu og Ufuk Topcu , “ Sandsynligvis cirka korrekt MDP-læring og kontrol med tidsmæssige logiske begrænsninger ”, arXiv: 1404.7073 [cs] ,28. april 2014( læs online , hørt den 5. december 2019 )
D. Sadigh , ES Kim , S. Coogan og SS Sastry , ” En lærer tilgang til kontrol syntese af Markov beslutningsprocesser for lineære tidsmæssig logiske specifikationer ”, 53. IEEE konference om beslutningen og kontrol ,december 2014, s. 1091–1096 ( DOI 10.1109 / CDC.2014.7039527 , læst online , adgang til 5. december 2019 )
(i) Giuseppe De Giacomo Luca Iocchi Marco Favorito og Fabio Patrizi , " Fundamenter til Fastholdelsesudstyr Bolte: Forstærkning Læring med LTLf / LdlF Fastholdende Specifikationer " , Proceedings of den internationale konference om Automated Planlægning og Planlægning , vol. 29,6. juli 2019, s. 128–136 ( ISSN 2334-0843 , læst online , adgang til 5. december 2019 )
Mohammadhosein Hasanbeig , Alessandro Abate og Daniel Kroening , " Logisk-begrænset neuralt monteret Q-iteration ", Forløb fra den 18. internationale konference om autonome agenter og MultiAgent-systemer , International Foundation for Autonomous Agents and Multiagent Systems, aAMAS '19,2019, s. 2012–2014 ( ISBN 978-1-4503-6309-9 , læst online , adgang til 5. december 2019 )
Rodrigo Toro Icarte , Toryn Q. Klassen , Richard Valenzano og Sheila A. McIlraith , ” Undervisning af flere opgaver til en RL-agent ved hjælp af LTL ”, Forhandlinger fra den 17. internationale konference om autonome agenter og MultiAgent-systemer , International Foundation for Autonomous Agents and Multiagent Systemer, aAMAS '18,2018, s. 452–461 ( læs online , hørt den 5. december 2019 )
“ Teoretiske spørgsmål i design og verifikation af distribuerede systemer | Guide books ” , på dl.acm.org ( DOI 10.5555 / 911361 , adgang 7. februar 2020 )
(da) A. Prasad Sistla , Moshe Y. Vardi og Pierre Wolper , “ Komplementeringsproblemet for Büchi automata med applikationer til tidsmæssig logik ” , Theoretical Computer Science , bind. 49, nr . 21 st januar 1987, s. 217–237 ( ISSN 0304-3975 , DOI 10.1016 / 0304-3975 (87) 90008-9 , læst online , adgang til 7. februar 2020 )
" SVAG MONADISK ANDEN BESTILLINGSTEORI AF ERFØLGER ER IKKE ELEMENTÆR-GENGENGENDE | Guide books ” , på dl.acm.org ( DOI 10.5555 / 889571 , adgang til 7. februar 2020 )

eksterne links