Esmakordselt avaldatud teisipäeval, 1. veebruaril 2007; sisuline läbivaatamine reedel, 25. jaanuaril 2019
Programmide loogika on modaalne loogika, mis tuleneb ideest seostada programmeerimiskeele iga arvutiprogrammiga α modaalsus. See idee tuleneb Engeleri [1967], Hoare [1969], Yanovi [1959] ja teiste tööde joonest, kes sõnastasid ja uurisid loogilisi keeli, milles saab väljendada programmi ühenduvuste omadusi. Algoritmiline loogika (AL), mille on esmakordselt välja töötanud Salwicki [1970], ja dünaamiline loogika (DL), mille töötas välja Pratt [1976], on nende tööde õige jätk. Keskendume siin DL-ile. Arvukad DL-ile ja selle variantidele pühendatud dokumendid ning selle mitmekesised rakendused programmi kontrollimisel ja andmestruktuuridel näitavad, et see on kasulik vahend programmide omaduste uurimisel. Pratt otsustas kujutada DL-i sellel, mida võib nimetada esmajärguliseks,ja see oli tema töö, mis käivitas Fischeri ja Ladneri [1979] määratleda DL-i ettepaneku variant paar aastat hiljem. See artikkel tutvustab DL-i pakkumisvariandi PDL-i.
1. Sissejuhatus
2. Mõisted ja põhimõttelised tulemused
2.1 Süntaks ja semantika
2.2 Aksiomatization ja täielikkus
2.3 Otsustatavus ja keerukus
3. Struktureeritud programmeerimine ja programmide õigsus
3.1 Hoare arvutus
3.2 Hoare arvutus ja PDL
3.3 Täielik õigsus
4. Mõned variandid
4.1 PDL ilma testideta
4.2 PDL koos vastupidisega
4.3 PDL kordamise ja silmustega
4.4 Ristmiku PDL
5. Järeldus
Bibliograafia
Akadeemilised tööriistad
Muud Interneti-ressursid
Seotud kirjed
1. Sissejuhatus
Dünaamiline loogika (DL) on modaalne loogika dünaamiliste süsteemide olekute ja sündmuste esitamiseks. DL-de keel on nii väitekeel, mis suudab väljendada arvutusolekute omadusi, kui ka programmeerimiskeel, mis suudab väljendada nende olekute vahelise süsteemisiirde omadusi. DL-id on programmide loogikad ja võimaldavad rääkida olukorrast, protsessidest, muutustest ja tulemustest.
Prati algne programmide dünaamiline loogika oli esimese järgu modaalne loogika. Propozicionaalne dünaamiline loogika (PDL) on sellele eelduslik vaste. Seda esitleti omaette loogikana väljaannetes Fischer ja Ladner [1979]. Algselt öeldes ei kasuta PDL-i keel termineid, predikaate ega funktsioone. Seega on PDL-is kaks süntaktilist kategooriat: ettepanekud ja programmid.
PDL-i lausetele tähenduse andmiseks töötame tavaliselt märgistatud siirdesüsteemide (LTS) abstraktse semantikaga. LTS-e võib vaadelda kui Kripke mudelite üldistust, kus maailmade või olekute vahelised üleminekud on märgistatud aatomiprogrammide nimedega. Hindamine näitab iga riigi kohta, millised väited selles tõesed on. Üleminek tähisega π ühest olekust x olekusse y - tähisega x R (π) y või (x, y) ∈ R (π) - näitab, et alustades x-st, on võimalik programmi π täitmine, mis lõpeb aastal y Kui väide A on tõene y-s, siis vastab valem A tõele x: st olekus x on võimalik programmi α täitmine, mis lõpeb A-d rahuldavas olekus. Üks tunneb ära modaalsuses, mis meenutab modaalloogika võimalikkuse (sageli märgitud ◊) modaalsust. Pole üllatav,on olemas ka vajalik vajaduse mõiste (mille modaalsust märgitakse sageli □). Valem [π] A on olekus x tõene, kui A on tõene igas olekus, mis on x-ga saavutatav üleminekuga tähistatud π.
Järgmisena võib keerukate programmide võimalikke täideviimisi määratleda kompositsiooniliselt. Näiteks programm “esimene α, siis β” on keeruline programm, täpsemalt jada. Võimalikku teostust saab kirjeldada LTS-is, koostades kaheastmelise ülemineku - siis ülemineku kohta, mida saab tähistada R (α; β) - olekute x ja x 'vahel: programmi on võimalik teostamine x-is α, mis lõpeb olekus y ja programmis β on võimalik teostada y, mis lõpeb x '. Kui väide A vastab tõele x '-is, siis on valem A olekus x tõene. Programmid α ja β võivad ise olla keerulised programmid. Veel saab programme väljendada rohkemate konstruktsioonidega, mida me õigeaegselt esitame.
Seejärel vaadatakse programmi laiendavalt: see on kahendsuhe LTS olekute paari vahel. Täpsemalt, see on vormi (x, y) paarikomplekt, mille abil saab programmi käivitada olekus x ja see võib viia olekusse y. Teisest küljest on pakkumine avaldus riigi kohta; olekus on see kas tõene või vale. Seega saab väidet vaadelda ka laiendavalt: LTS-i olekute kogum, kus see on tõene.
Akronüümiga PDL viitame siin täpselt propositsioonilisele dünaamilisele loogikale järgmiste programmi konstruktidega: jada, mittedeterministlik valik, piiramatu iteratsioon ja test. Tutvustame seda jaotises 2 koos mõningate omaduste ja põhitulemustega. Eelkõige käsitleme selle aksiomatization ja selle otsustusvõimet.
Hoare'i [1969] arvutatud Hoare'i arvutus on orienteeritud programmide loogikale. See puudutab vormi {A} α {B} väidete tõesust - tähendades, et eeltingimusega A on programmis α alati B kui eeltingimus ja see on määratletud aksiomaatiliselt. See tuleneb rangete meetodite soovist programmide omaduste üle mõtiskleda ja seeläbi programmeerimise tegevusele teatud koht teaduse valdkonnas anda. Burstall [1974] nägi modaalse loogika ja programmide mõttekäigu analoogiat, kuid tegelik töö selle kallal sai alguse Prattist (1976), kui seda soovitas talle tolleaegne õpilane R. Moore. PDL pärineb Prati tõlgendusest Hoare arvutusest modaalloogika formalismis. Sissejuhatuse PDL-i geneesi võib leida Prattist [1980b]. Hoare-kolmik {A} α {B} on hõivatud PDL valemiga A → [α] B, mis tähendab sõna-sõnalt, et kui A on tõene, siis iga α edukalt lõpetav teostus lõpeb sellega, et B on tõene. Selle ühenduse loomisel on rutiinne tõestada Hoare arvutuse algreegleid, kasutades eranditult PDL-i aksiomatizationi. Seda teeme üksikasjalikult 3. osas, mis keskendub struktureeritud programmide õigsuse mõttekäigule.
PDL-iga seotud täiendavad teemad hõlmavad tulemusi, mis käsitlevad PDL-i mitmel viisil laiendamise või piiramisega saadud paljude huvitavate variantide väljendusvõimet, otsustatavust, keerukust ja täielikkust. Alates selle loomisest on tähelepanu pööratud paljudele PDL-i variantidele. Need variandid võivad hõlmata deterministlikke programme, piiratud teste, mitteregulaarseid programme, programme automaatidena, programmide täiendamist ja ristumist, vastupidiseid ja lõpmatuid arvutusi jne. Mõned neist on esitatud 4. osas, pakkudes näpunäiteid nende suhtelise ekspressiivsuse kohta, nende aksiomatizations ja nende arvutuslik keerukus.
Me järeldame 5. jaos.
2. Mõisted ja põhimõttelised tulemused
Esitame PDL-i süntaksi ja semantika jaotises 2.1. PDL-i tõestusteooria on esitatud jaotises 2.2 koos axiomatizations ja viidetega kirjandusele terviklikkuse kohta. Otsustatavuse ja keerukuse probleemi käsitleme jaotises 2.3.
2.1 Süntaks ja semantika
Propozicionaalne dünaamiline loogika (PDL) on ette nähtud programmide pakkumisomaduste esindamiseks ja põhjendamiseks. Selle süntaks põhineb kahel sümbolikomplektil: loendatav aatomivalemite kogum Φ 0 ja aatomiprogrammide loendatav hulk Π 0. Selle baasi keerulised valemid ja kompleksprogrammid on määratletud järgmiselt:
Iga aatomivalem on valem
0 (“vale”) on valem
Kui A on valem, siis ¬ A (“mitte A”) on valem
Kui A ja B on valemid, siis (A ∨ B) (“A või B”) on valem
Kui α on programm ja A on valem, siis on α] A ("iga α täideviimine praegusest olekust viib olekusse, kus A on tõene") on valem
Iga aatomiprogramm on programm
Kui α ja β on programmid, siis (α; β) („do α järgneb β”) on programm
Kui α ja β on programmid, siis (α∪β) („tehke α või β, mittedeterministlikult”) on programm,
Kui α on programm, siis α * (“korrake α piiratud, kuid mittedeterministlikult määratud kordade arv”) on programm.
Kui A on valem, siis A? (“Jätkake, kui A on tõene, muidu ei õnnestu”) on programm
Teisi Boole ühendusi 1, ∧, → ja ↔ kasutatakse lühenditena tavapärasel viisil. Lisaks lühendame ¬ [α] ¬ A-st A-ni („α teatav täideviimine praegusest olekust viib olekusse, kus A on tõene”) nagu modaalloogikas. Kirjutame α n α jaoks;…; α n esinemisega α. Rohkem ametlikult:
α 0 = df 1?
α n +1 = df α; α n
Samuti:
α + = df α; α *
on sageli kasulik iteratsiooni esitamiseks, mis on piirideta, kuid esineb vähemalt üks kord. Lõpuks võtame vastu sulgude väljajätmise standardreeglid.
Valemite abil saab kirjeldada atribuute, mis säilivad pärast programmi edukat täitmist. Näiteks valem [α∪β] A tähendab, et alati, kui programmi α või β edukalt täidetakse, jõutakse olekusse, kus A hoiab, samas kui valem A tähendab, et α ja β vahelduvate täideviimiste jada on selline, et a olekusse jõutakse seal, kus A hoiab. Semantiliselt öeldes tõlgendavad valemeid olekukogumid ja programme tõlgendavad binaarsuhted üleminekusüsteemi olekute vahel. Täpsemalt tõlgendatakse PDL-i valemite ja programmide tähendust märgistatud siirdesüsteemide (LTS) kaudu M = (W, R, V), kus W on maailmade või olekute tühine kogum, R on aatomi hulga Π 0 kaardistamine. Programmid binaarsuheteks W ja V puhul on kaardistamine hulgast Φ 0 aatomivalemite arv W alamrühmadesse.
Mitteametlikult omistatakse kaardistamisele R igale aatomiprogrammile π ∈ some 0 mingi binaarsuhe R (π) W-l, mille tähendus on x R (π) y, kui eksisteerib arv π x-st, mis viib y-ni, samas kui kaardistamine V määrab igale aatomvalemiga p ∈ Φ 0 W osa alamhulga V (p), mille kavandatud tähendus on x ∈ V (p), kui p on tões x. Arvestades näituid 0, ¬ A, A ∨ B, [α] A, α; β, α β, α * ja A,, on selge, et R ja V tuleb induktiivselt laiendada järgmiselt, et saada kavandatud tähendused keerukate programmide ja valemite jaoks:
x R (α; β) y, kui eksisteerib maailm z, nii et x R (α) z ja z R (β) y
xR (α∪β) y, kui xR (α) y või xR (β) y
x R (α *) y, kui eksisteerib mittenegatiivne täisarv n ja on olemas maailmu z 0,…, z n, nii et z 0 = x, z n = y ja kõigi k = 1.. n, z k −1 R (α) z k
x R (A?) y, kui x = y ja y ∈ V (A)
V (0) = ∅
V (¬ A) = W \ V (A)
V (A ∨ B) = V (A) ∪ V (B),
V ([α] A) = {x: kõigi maailmade y korral, kui x R (α) y, siis y ∈ V (A)}
Kui x ∈ V (A), siis ütleme, et A on rahul olekus x M-is või “M, x sat A”.
Kaks samalaadset LTS-i
Helistage M ülal vasakul kujutatud LTS-ile ja M 'paremal kujutatud LTS-ile. Formaalselt määratletud on meil M = (W, R, V) koos W = {x 1, x 2 }, R (π 1) = {(x 1, x 1)}, R (π 2) = {(x 1, x 2)}, V (p) = {x 1 }, V (q) = {x 2 } ja meil on M '= (W', R ', V') koos W '= {y 1, y 2, y 3, y 4 }, R (π 1) = {(y 1, y 2), (y 2, y 2)}, R '(π2) = {(y 1, y 3), (y 2, y 4)}, V '(p) = {y 1, y 2 }, V' (q) = {y 3, y 4 }. Meil on näiteks:
M, x 1 laup
M, x 2 sat q
M, x 1 sat <π 1 > p ∧ <π 2 > q
M, x 1 küllastatud [π 1] p ∧ [π 1 *] lk
M ', y 1 sat <π 1 *; π 2 > q
M ', y 2 sat [π 1 *] lk
M ', y 1 sat [π 1 1π 2] (q ∨ p)
M ', y 3 sat [π 1 ∪π 2] 0
Vaatleme nüüd valemit A. Me ütleme, et A kehtib M-is või et M on A või “M ⊨ A” mudel, kui tegemist on kõigi maailmadega x, x ∈ V (A). A öeldakse kehtivana või “⊨ A”, kui tegemist on kõigi mudelitega M, M ⊨ A. Me ütleme, et A on rahuldatav M-is või et M rahuldab A-d või “M sat A”, kui eksisteerib maailm x, näiteks x ∈ V (A). A-d öeldakse olevat rahuldav või "sat A", kui on olemas mudel M, näiteks M sat A. Huvitav
sat Aff ei ole ¬ ¬ A
⊨ Aff ei sat ¬ A
Mõni tähelepanuväärne PDL valem on kehtiv. (Lugeja võib proovida neid formaalselt tõestada või vähemalt hakata veenma ennast ülaltoodud väheste näidete põhjal.)
⊨ [α; β] A ↔ [α] [β] A
⊨ [α∪β] A ↔ [α] A ∧ [β] A
⊨ [α *] A ↔ A ∧ [α] [α *] A
⊨ [A?] B ↔ (A → B)
Samaväärselt võime neid kirjutada kahesuguse vormi all.
⊨ A ↔ A
⊨ A ↔ A ∨ A
⊨ A ↔ A ∨ A
⊨ <A?> B ↔ A ∧ B
Üks huvitav mõte on seotud PDL-i valemiga väljendatud teabe hulgaga, mis sisaldub LTS-is. LTS-is kirjeldatud süsteemi käitumine on selle vormis tõepoolest sageli pisut varjatud. Näiteks on lihtsal kontrollimisel lihtne veenda, et kahel ülaltoodud LTS-il on sama käitumine ja nad vastavad samadele PDL-i valemitele. Selle süntaksi ja semantika jaotise lõpuleviimiseks anname nende väidete teoreetilise aluse.
Arvestades kahte LTS-i, võib küsida, kas need vastavad samadele valemitele. Bisimulatsiooni mõiste on muutunud Kripke mudelite ja märgistatud üleminekusüsteemide samaväärsuse standardmõõduks. Bisimulatsioon LTSide M = (W, R, V) ja M '= (W', R ', V') vahel on binaarsuhe Z nende olekute vahel nii, et kõigi maailmade M korral M ja kõigi maailmade x 'vahel M-is, kui xZx ', siis
kõigi aatomvalemite korral p ∈ Φ 0, x ∈ V (p) iff x '∈ V' (p)
kõigi aatomiprogrammide π ∈ Π 0 ja kõigi maailmade y korral M-s, kui x R (π) y, siis eksisteerib maailmas y 'M-is, nii et yZy' ja x 'R' (π) y '
kõigi aatomiprogrammide π ∈ Π 0 ja kõigi maailmade y 'jaoks M-s, kui x' R '(π) y', siis eksisteerib M-s maailm y, nii et yZy 'ja x R (π) y
Me ütleme, et kaks LTS-i on samalaadsed, kui nende vahel on bisimulatsioon. PDL-i algusest peale on teada, et kahes samalaadses LTS-is M ja M ', kõigi maailmade x korral M-s ja kõigi maailmade x' M-i korral, kui xZx ', siis kõigi PDL-i valemite A, x ∈ V (A) korral. iff x '∈ V' (A). Seega, kui kaks LTS-i on bisimulatsiooni määratluse kohaselt ülaltoodud bisimilaarsed, on nii, et kui xZx '
kõigi programmide α ja kõigi maailmade y korral M-s, kui x R (α) y, siis eksisteerib maailmas y 'M' -is selliselt, et yZy 'ja x' R '(α) y'
kõigi programmide α ja kõigi maailmade y 'jaoks M-s, kui x' R '(α) y', siis eksisteerib M-s maailm y, nii et yZy 'ja x R (α) y
Seega saab lihtsalt võrrelda kahe LTS-i käitumist, kontrollides ainult aatomiprogramme ja turvaliselt ekstrapoleerida nende LTS-ide võrdlevat käitumist isegi keerukate programmide puhul. Me ütleme, et PDL programmi konstruktid on bisimulatsiooni jaoks ohutud. Bisimulatsiooniks ohutute programmikonstruktsioonide täpse iseloomustamise kohta vt Van Benthem [1998].
On selgelt näha, et kaks ülaltoodud LTS-i juhtumit on samalaadsed. Bisimulation Z vahel M ja M 'võib manustada: Z = {(x 1, y 1), (x 1, y 2), (x 2, y 3), (x 2, y 4)}. Olekud x 1 ja y 1 vastavad täpselt samadele PDL valemitele. Nii tehke olekud x 1 ja y 2 jne.
2.2 Aksiomatization ja täielikkus
Tõestusteooria eesmärk on anda omadusele ⊨ A iseloomustus aksioomide ja järelduse reeglite osas. Selles jaotises määratleme lahutatavuse predikaadi ⊢ induktiivselt valemitega tehtavate operatsioonide abil, mis sõltuvad ainult nende süntaktilisest struktuurist nii, et kõigi valemite A korral
I Aff ff A.
Muidugi on PDL klassikalise propositsioonilise loogika laiendus. Kõigepealt eeldame, et kõik väidetavad tautoloogiad kehtivad ja kõik väidetavad põhjendused on lubatud. Eelkõige on modus ponens kehtiv reegel: punktidest A ja A → B järeldavad B. Mis tahes programmi α korral, piirates LTS-i suhtega R (α), saame Kripke'i mudeli, kus modaalsuse loogika on kõige nõrgem normaalmodaalne loogika, nimelt loogika K. Seega sisaldab PDL iga juhtumit tuttava jaotuse aksioomi skeemist:
(A0) [α] (A → B) → ([α] A → [α] B)
ja see on suletud järgmise järelduse reegli (vajaduse reegel) alusel:
(N) alates A järeldada [a] A.
Modaalloogika on normaalne, kui see kuuletub (A0) ja (N). Kõigi α jaoks on olulised omadused, et [α] jaotub konjunktsioonis ∧, ja saab tõestada monotoonsuse reeglit, mis lubab A → B-st järeldada [α] A → [α] B-d. Lõpuks on PDL kõige vähem tavaline modaalloogika, mis sisaldab järgmiste aksioomiskeemide kõiki eksemplare
(A1) [α; β] A ↔ [α] [β] A
(A2) [α∪β] A ↔ [α] A ∧ [β] A
(A3) [α *] A ↔ A ∧ [α] [a *] A
(A4) [A?] B ↔ (A → B)
ja suletakse järgmise järelduse reegli (silmuse invariantsi reegel) alusel:
(I) punktist A → [a] A järeldada A → [α *] A
Kui X on valemite kogum ja A on valem, siis ütleme, et A on X-st tuletatav or või “X ⊢ A”, kui on olemas valemite jada A 0, A 1,…, A n, nii et n = A ja iga i ≤ n A i on näiteks aksioom skeemi või valemiga X või pärineb varasem valemitega järjestuse järgi reeglina järeldusmootorite. Lisaks: i Aff ∅ ⊢ A; sel juhul ütleme, et A on ⊢-deduktiivne. Xi peetakse ⊢-järjepidevaks, kui mitte X X 0. Lihtne on kindlaks teha, et (I) saab asendada järgmise aksioomiskeemiga (induktsiooni aksioomiskeem):
(A5) [α *] (A → [α] A) → (A → [α *] A)
Teeme kõigepealt kindlaks, et (I) on tõestussüsteemi tuletatud reegel, mis põhineb punktidel (A1), (A2), (A3), (A4) ja (A5):
1
A → [a] A
eeldus
2
[α *] (A → [α] A)
alates 1 kasutades (N)
3
[α *] (A → [α] A) → (A → [α *] A)
aksioomiskeem (A5)
4
A → [α *] A
alates 2 ja 3, kasutades modus ponensi
Järgmisena tõestame, et (A5) on ⊢ -arvatav:
1
[α *] (A → [α] A) ↔ (A → [α] A) ∧ [α] [α *] (A → [α] A)
aksioomiskeem (A3)
2
A ∧ [α *] (A → [α] A) → [α] (A ∧ [α *] (A → [α] A))
alates 1, kasutades algset arutlust ja [α] jaotust ∧ suhtes
3
A ∧ [α *] (A → [α] A) → [α *] (A ∧ [α *] (A → [α] A))
alates 2 kasutades (I)
4
[α *] (A → [α] A) → (A → [α *] A)
3-st, kasutades algset mõttekäiku ja [α *] jaotust ∧ suhtes
PDL-i aksiomatization aksioomiskeemide (A1), (A2), (A3), (A4) ja (A5) alusel on tehtud Segerbergis [1977]. Ülaltoodud definitsioonidest nähtub, et ⊢ on ⊨ suhtes kindel, st
Kõigi valemite A korral, kui ⊢ A, siis ⊨ A
Tõestamine toimub induktsiooni teel A-i deduktsiooni pikkusega ⊢. Of täielikkuse küsimus ⊨ suhtes, st
Kõigi valemite A korral, kui ⊨ A, siis ⊢ A
jälitasid mitmed loogikud. Segerbergis [1977] esitatud mõttekäik oli esimene katse tõestada ⊢-i täielikkust. Varsti jõudis ka Parikh tõenduseni. Kui 1978. aasta alguses leidis Segerberg oma väites vigu (mille ta lõpuks parandas), avaldas Parikh seda, mida võib pidada esimeseks tõendiks of täielikkuse kohta Parikhis [1978]. Pärast published täielikkust on avaldatud erinevaid tõendeid, nt Kozen ja Parikh [1981].
Samuti on otsitud erinevaid alternatiivseid PDL-i tõestusteooriaid. Isegi varakult, eriti Prattis [1978]. Mainigem siis ka Nishimura [1979] ja Vakarelov [1983] seotud teooriate täielikkust.
PDL-i mahaarvatavuse predikaadi alternatiivne formulatsioon võimaldab kasutada infinitaarset järelduse reeglit, nagu näiteks Goldblatt [1992a]. (Infinitaarne järeldusereegel võtab lõpmatu arvu ruume.) Olgu ⊢ 'mahaarvatavuse predikaat, mis vastab väites dünaamilise loogika keeles kõige vähem tavalisele modaalloogikale, mis sisaldab aksioomiskeemide kõiki juhtumeid (A1), (A2). (A3) ja (A4) ning suletakse vastavalt järgmisele infinitaarsele järeldusele:
(I ') alates {[β] [α n] A: n ≥ 0} järeldada [β] [α *] A
Võib tõestada, et ⊢ 'on ühtaegu kindel ja täielik and suhtes, st
Kõigi valemite A korral on A 'iff ⊨ A
Teisisõnu, kõigi kehtivate valemite komplekti genereerimisel on tõestussüsteemid ⊢ ja ⊢ 'ekvivalentsed.
2.3 Otsustatavus ja keerukus
Keerukusteooria eesmärk on tuvastada vara A arvutatavus aja või ruumi ressursside osas. Loogika L keerukust seostatakse sageli valemi rahuldatavuse otsustamise probleemiga, mida määratletakse järgmiselt:
(L-SAT) Kas valemi A korral on A rahuldav?
Selles jaotises uurime järgmise otsuseprobleemi keerukust:
(PDL-SAT) Kas PDL valemi A korral on A rahuldav?
PDL täielik aksiomatization on kehtivate PDL valemite komplekti või teisisõnu valemi komplekti, mille eitamine ei ole rahuldav, rekursiivne määratlus. Seega on probleemiga (PDL-SAT) seotud alamprotseduur, mis vastaks eitavalt, kui PDL valem A ei oleks rahuldav. Alamprotseduur (SP1) koosneb kõigi ⊢-tuletatavate valemite loetlemisest, alustades aksioomidest ja järeldades teiste reeglite abil teoreeme. Piisava aja olemasolul leiaks alamprotseduur lõpuks valemi, kui formula-deduktiivne oleks. Seega, kui A pole rahuldav, peab (SP1) lõpuks leidma ¬A ja vastama eitavalt.
Kui valem A on rahuldav, siis (SP1) ei leita kunagi ¬ A. See kestab igavesti ja selles ei saa kunagi kindel olla. Kuid sellest ebakindlusest on väljapääs. Võime mõelda ka teisele alaprotseduurile, mis vastab jaatavalt, kui PDL valem on rahuldav. PDL-i üks varasemaid tulemusi oli tõestus sellest, et PDL-il on lõppenud mudeli omadus, st
Kõigi valemite A korral, kui sat A, on olemas lõplik mudel M, näiteks M sat A.
Lõpliku mudeli omadus pakub aluse protseduuriks (SP2), mis seisneb PDL-i lõplike mudelite ükshaaval loetlemises ja testimises, kas üks neist vastab valemile. (Kõigi valemite A ja kõigi piiratud mudelite M puhul on lihtne testida, kas M täitis A, kasutades V (A) definitsiooni.) Seega, kui A on rahuldatav, peab ta lõpuks leidma mudeli M, nii et M sat A ja vastake jaatavalt. Sümmeetriliselt esimese alaprotseduuri (SP1) korral, kui valem A pole rahuldav, siis (SP2) ei leia kunagi seda rahuldavat mudelit, see töötab igavesti ja selles ei saa kunagi kindel olla.
Nüüd (SP1) ja (SP2) kombineerides on meil võimalus otsustada, kas PDL valem A on rahuldav. Piisab nende paralleelsest käitamisest: kui A on rahuldav, vastab (SP2) lõpuks jah, kui A ei vasta, siis (SP1) vastab lõpuks ei. Protseduur peatub, kui kas (SP1) või (SP2) annab vastuse.
Kui saadud protseduurist piisab järeldusele, et probleem (PDL-SAT) on lahendatav, on see praktikas väga ebaefektiivne. Selle tulemus on Fischeri ja Ladneri [1979] ning Kozeni ja Parikhi [1981] tõttu tugevam kui piiratud mudeli omadus, see on väikese mudeli omadus:
Kõigi valemite A korral, kui sat A, on olemas lõplik mudel M, mille suurus A on eksponentsiaalne, nii et M sat A.
See tähendab, et me teaksime nüüd, millal lõpetada protseduuri valemile vastava mudeli otsimine (SP2). Seega saame (SP2) abil testida, kas valem on rahuldav, kuid kui oleme kõik väikesed mudelid ammendanud, võime järeldada, et valem ei ole rahuldav. Selle tulemuseks on protseduur, mis töötab mittedeterministlikult eksponentsiaalse aja jooksul (NEXPTIME): arvake kõige suurema eksponentsiaaliga suurusmudel ja kontrollige, kas see vastab valemile. Kuid PDL keerukuse teooria peamised tulemused pärinevad Fischerilt ja Ladnerilt [1979] ja Prattilt [1980a]. Jälgides, et PDL-i valem võib tõhusalt kirjeldada lineaarruumiga piiratud vahelduva Turingi masina arvutamist, lõid Fischer ja Ladner [1979] kõigepealt (PDL-SAT) eksponentsiaalaja alumise piiri. EXPTIME ülemine piir (PDL-SAT) on saadud Prattilt [1980a],kes kasutas tableaux meetodi PDL-i ekvivalenti. Seega (PDL-SAT) on EXPTIME-täielik. (De Giacomo ja Massacci [2000]) pakuvad välja praktikas efektiivsema algoritmi, mis halvimal juhul töötab endiselt determinantse eksponentsiaalse aja jooksul.)
3. Struktureeritud programmeerimine ja programmide õigsus
Ajalooliselt tuleneb programmide loogika 1960. aastate lõpul arvutiteadlaste tööst, kes olid huvitatud programmeerimiskeelte tähenduse omistamisest ja programmide tõestuste range standardi leidmisest. Näiteks võivad sellised tõendid olla programmi õigsuse osas eeldatava käitumise suhtes või programmi lõpetamise kohta. Algdokument on Floyd [1967], kus on esitatud struktureeritud arvutiprogrammide omaduste analüüs vooskeemide abil. Mõned varasemad tööd, näiteks Yanov [1959] või Engeler [1967], olid arendanud ja õppinud ametlikke keeli, milles saab väljendada programmi ühenduste omadusi. Hoare [1969] formalism oli verstapostiks PDL-i tulekul. See pakuti välja Floydi vooskeemide range aksiomaatilise tõlgendusena. Me räägime sageli Hoare loogikast või Floyd-Hoare loogikast,või Hoare calculus sellele formalismile viidates. Hoare arvutus on seotud väidete tõesusega („Hoare kolmikud”), näiteks {A} α {B}, mis loob seose eeltingimuse A, programmi α ja eeltingimuse B vahel. See näitab, et kui A on α täitmise eeltingimus, siis B on pärast α edukat täitmist eeltingimus.
See oli tõsi paar aastakümmet tagasi ja on endiselt nii: programmi valideerimine toimub sagedamini, kui seda testida mõistliku sisendiga. Kui sisend ei anna oodatud väljundit, “viga” fikseeritakse. Kui lõpuks saadakse iga testitud sisendi jaoks eeldatav väljund, siis on põhjust uskuda, et programmis pole viga. Kuid see on aeganõudev valideerimismeetod ja see jätab ruumi katsetamata sisenditele, mis ebaõnnestuks. Nende vigade leidmine pärast programmi juurutamist ja kasutuselevõtmist on ressursside jaoks veelgi kulukam. Programmi õigsuse põhjendamine ametlike meetoditega on kriitiliste süsteemide jaoks ülioluline, kuna see annab võimaluse tõestada ammendavalt, et programmis pole vigu.
3.1 Hoare arvutus
Hoare arvutustes reeglitega haaratud programmide põhimõtete illustreerimiseks piisab, kui tutvuda mõnega neist. (NB! Reeglid tähendavad, et kui kõik reegli rea kohal olevad väited kehtivad - ruumid -, siis kehtib ka reegli rea all olev avaldus -).
{A} α 1 {B} {B} α 2 {C}
(koosseisu reegel)
{A} ai 1; α 2 {C}
Kompositsioonireegel hõlmab programmide elementaarset järjestikust kompositsiooni. Ruumidena on meil kaks eeldust kahe programmi α 1 ja α 2 osalise õigsuse kohta. Esimene eeldus on, et kui α 1 täidetakse A-d rahuldavas olekus, siis lõpeb see B-i rahuldavas olekus, kui see peatub. Teine eeldus on, et kui α 2 täidetakse olekus, mis rahuldab B, siis lõpeb see seisundis, mis rahuldab C, kui see peatub. Reegli järeldus on programmi α 1; α 2 osaline õigsus (st α 1, mis koosneb järjestikust α 2-st)), mis tuleneb kahest eeldusest. Nimelt võime järeldada, et kui α 1; α 2 täidetakse A-d rahuldavas olekus, siis lõpeb see C-d rahuldavas olekus, kui see peatub.
Kordumise reegel on oluline, kuna see haarab programmide olulist võimet mõnda koodi osa korduvalt täita, kuni teatud tingimus enam ei kehti.
{A ∧ B} α {A}
(iteratsiooni reegel)
{A}, samal ajal kui B teeb α {¬ B ∧ A}
Lõpuks on kaks tagajärjereeglit olulised, et anda formaalne alus intuitiivselt selgetele mõttekäikudele, mis hõlmavad vastavalt nõrgemaid eeltingimusi ja tugevamaid eeltingimusi.
{A} α {B} B → C
(1. tagajärje reegel)
{A} α {C}
C → A {A} α {B}
(2. tagajärje reegel)
{C} α {B}
Hoare'is [1969] esitatud formaalsusest jätame selle aksioomiskeemid välja, kuna see eeldaks esimese astme keelt. Lõpuks lisatakse Hoare loogika hilisemas töös sageli ka rohkem reegleid. Vaadake varase ülevaate saamiseks Apt [1979].
3.2 Hoare arvutus ja PDL
Dünaamiline loogika tuleneb Prati tõlgendusest Hoare kolmikutele ja Hoare calculusele modaalse loogika formalismis. Modaalsusega [α] saame formaalselt väljendada, et kõik α täitmisega saavutatavad olekud vastavad valemit A. Selleks kirjutatakse [a] A. Seega on Hoare kolmik {A} α {B} lihtsalt PDL valemi abil hõivatud
A → [a] B
Lisaks saab olulisi programmeerimiskonstruktsioone PDL-is hõlpsasti sisse tuua määratletava lühendi abil:
kui A, siis α muidu β = df ((A?; α) ∪ (¬ A?; β))
samal ajal kui A do α = df ((A?; α) *; ¬ A?)
korda α, kuni A = df (α; ((¬ A; α) *; A?))
katkesta = df 0?
vahele = df 1?
Seega näib, et PDL-iga oleme hästi varustatud, et loogiliselt tõestada struktureeritud programmide õigsust. Lisaks PDL-i ja Hoare calculuse vahelisele küllaltki kätega vehkimisele pole võib-olla veel selge, kuidas need formaalselt seostuvad. PDL on tegelikult Hoare calculuse üldistus selles mõttes, et kõiki Hoare calculuse reegleid saab tõestada PDL aksomaatilises süsteemis. (Rangelt öeldes sisaldab Hoare'i kalkulatsioon aksioome, mis nõuaksid esimese järgu dünaamilise loogika laiendatud keelt.) See on üsna tähelepanuväärne, nii et näitame siin näitena kahte ülaltoodud reeglit.
Tõestused algavad reeglite eeldustest. Seejärel, kasutades neid eeldusi, PDL-i aksioome ja reegleid ning mitte midagi muud, on eesmärk kindlaks teha, kas reeglite sõlmimine loogiliselt järgib. Seega alustame kompositsioonireegli puhul eeldusega, et PDL-i sõnastuses on {A} α 1 {B}, see tähendab A → [α 1] B, ja eeldades, et {B} α 2 {C}, see on B → [α 2] C. Eesmärk on tõestada, et {A} α 1; α 2 {C}. Täpsemalt tahame teha kindlaks, et A → [α 1; α 2] C on ⊢ -tahutav valemite {A → [α 1] B, B → [α 2] C} hulgast.
1
A → [α 1] B
eeldus {A} α 1 {B}
2
B → [a 2] C
eeldus {B} α 2 {C}
3
[a 1] B → [a 1] [a 2] C
Alates 2, kasutades [α 1] monotoonsust
4
A → [a 1] [a 2] C
alates 1 ja 3, kasutades juhendpõhimõtteid
5
[a 1; a 2] C ↔ [a 1] [a 2] C
aksioomiskeem (A1)
6
→ [α 1; α 2] C
alates 4 ja 5, kasutades ettepanekul põhinevat arutlust
-
{A} α 1; α 2 {C}
Ineratsioonireegli tõestus on pisut rohkem seotud.
1
A ∧ B → [α] A
eeldus {A ∧ B} α {A}
2
A → (B → [α] A)
alates 1, kasutades ettepanekul põhinevat arutlust
3
[B?] [A] A ↔ (B → [a] A)
aksioomiskeem (A4)
4
A → [B?] [A] A
alates 2 ja 3, kasutades ettepanekul põhinevat arutlust
5
[B?; α] A ↔ [B?] [a] A
aksioomiskeem (A1)
6
A → [B?; A] A
alates 4 ja 5, kasutades ettepanekul põhinevat arutlust
7
A → [(B?; A) *] A
alates 6 kasutades (I)
8
A → (¬ B → (¬ B ∧ A))
propositsiooniline tautoloogia
9
A → [(B?; Α) *] (¬ B → (¬ B ∧ A))
7 ja 8, kasutades [(B?; α) *] monotoonsust ja ettepanekul põhinevat arutlust
10.
[¬B?] (¬B ∧ A) ↔ (¬B → (¬B ∧ A))
Aksioomi skeem (A4)
11
A → [(B?; Α) *] [¬B?] (¬B ∧ A)
9 ja 10, kasutades [(B?; α) *] monotoonsust ja ettepanekul põhinevat arutlust
12.
[(B?; A) *; ¬B?] (¬B ∧ A) ↔ [(B?; Α) *] [¬B?] (¬B ∧ A)
aksioomiskeem (A1)
13.
A → [(B?; A) *; ¬B?] (¬B ∧ A)
alates 12, kasutades ettepanekul põhinevat arutlust
-
{A}, samal ajal kui B teeb α {¬ B ∧ A}
PDL-i kontekstis on kaks tagajärgede reeglit tegelikult koosseisu reegli erijuhud. Et saada esimene reegel, asendada α 1 ja α ja α 2 koos skip. Et saada teine reegel, asendada α 1 ja vahelejätmise ja α 2 koos α. Piisab, kui rakendada aksioomiskeemi (A4) ja märkida, et [α; jätke vahele A '[a] A ja [a; vahele jäta] A ↔ [α] A on ka ci -arvatavad kõigi A ja kõigi α korral.
3.3 Täielik õigsus
Hoare enda sisseastumisel Hoaresse [1979] oli tema algne arvutus ainult lähtepunkt ja tal oli mitmeid piiranguid. Eelkõige võimaldab see osalise õigsuse üle järele mõelda vaid üht. See tähendab, et väite {A} α {B} tõde tagab ainult selle, et kõik α hukkamised, mis algavad A-d rahuldavas olekus, lõpevad B-d rahuldavas olekus või ei peatu. See tähendab, et osaliselt õiges programmis võivad olla lõpetamata täitmised. (Tegelikult on programm, millel pole lõpetavat täitmist, alati osaliselt õige. See kehtib näiteks programmi kohta, kui üks jätab vahele. Valem A → [ samal ajal kui 1 jätab vahele] B on tuletatav kõigi valemite A ja B korral.) Arvutus ei anna alust programmi lõppemise tõendiks. Seda saab muuta nii, et see arvestaks programmide täielikku õigsust: osaline õigsus ja lõpetamine. See saavutatakse iteratsioonireegli muutmisega. Me ei esita seda siin ja suuname huvitatud lugeja Apt [1981] juurde.
Vaatleme kõigepealt, et deterministlike programmide puhul saab juba täielikku õigsust hõivata sedalaadi valemite abil
A → B
Lause B tähendab, et toimub α-teostus, mis lõpeb olekus, mis rahuldab B-d. Veelgi enam, kui α on deterministlik, on see võimalik lõpetav teostus α kordumatu täitmine. Seega, kui õnnestub kõigepealt tõestada, et programm on deterministlik, töötab see trikk selle täieliku õigsuse tõestamiseks piisavalt hästi.
Üldine lahendus täieliku õigsuse probleemile eksisteerib PDL-is. Kuid me peame seda natuke laiendama. Pratt osutas Prattis juba [1980b], et PDL pole piisavalt ekspressiivne, et haarata programmide lõpmatut silmust. Reaktsioonina esitas Streett [1982] korduva PDL (RPDL). See sisaldab kõigi programmide α jaoks avaldist Δα, mis tähistab uut semantilisi ettepanekuid
V (αα) = {x: on olemas lõpmatu jada x 0, x 1,… olekut, nii et x 0 = x ja kõigi n ≥ 0, x n R (α) x n +1 }
Streett [1982] arvas, et RPDL-i saab aksiomatiziseerida, lisades PDL-i tõestussüsteemile täpselt järgmised aksioomiskeemid.
(A6) Δα → Δα
(A7) [α *] (A → A) → (A → Δα)
Oletuse tõendusmaterjal on esitatud Sakalauskaites ja Valievis [1990]. (Kombinatiivse PDL variandi oletusversiooni tõestas ka Gargov ja Passy [1988].)
On lihtne mõista, et ülaltoodud Hoare arvutustes võib lõpetamise lõpetamine tuleneda ainult iteratsiooni reeglist. Analoogselt võib PDL-programmi lõpetamata jätmine tuleneda ainult piiramatu iteratsiooni kasutamisest. Lause Δα näitab, et α * võib erineda ja see on just selline mõiste, mida me vajame. Nüüd saame induktiivselt määratleda predikaadi ∞ nii, et programmi α korral vastab valem ∞ (α) täpselt siis, kui α saab sisestada lõpmatu arvutuse.
∞ (π): = 0 kus π ∈ Π 0
∞ (φ?): = 0
∞ (α ∪ β): = ∞ (α) ∨ ∞ (β)
∞ (α; β): = ∞ (α) ∨ ∞ (β)
∞ (α *): = Δα ∨ ∞ (α)
Lõpuks saab programmi täielikku õigsust väljendada samalaadsete valemite abil
A → (¬∞ (α) ∧ [α] B)
mis tähendab sõna-sõnalt, et kui see on A, siis ei saa programm α igavesti joosta ja iga edukas teostus lõppeb olekus, mis rahuldab B-d.
4. Mõned variandid
Mitmete PDL-i variantide süntaksi ja semantika laiendamise või piiramise teel saadud variantide väljendusvõime, otsustatavuse, keerukuse, aksiomatiziseerituse ja täielikkuse võrdlusvõimega seotud tulemused on rohke kirjanduse teema. Me võime öelda ainult nii palju ja käsitleme vaid mõnda neist variantidest, jättes dünaamilises loogikas välja muidu olulise töö suured tükid.
4.1 PDL ilma testideta
Aksioomiskeem [A?] B ↔ (A → B) näib viitavat, et iga valemi C jaoks on olemas samaväärne testivaba valem C '-ie, on olemas testivaba valem C', nii et that C ↔ C '. Huvitav on tõdeda, et see väide ei ole tõene. Olgu PDL 0 piiratud PDL-iga testivabadele tavaprogrammidele, st programmidele, mis ei sisalda teste. Berman ja Paterson [1981] pidasid PDL valemit <(p?; Π) *; ¬ p?; Π; p?> 1, mis on
< samal ajal kui p do π> p
ja tõestas, et sellele pole samaväärset PDL 0 valemit. Seega PDL on rohkem väljendusrikas energiat kui PDL 0. Nende argumente saab üldistada järgmiselt. Kõigi n ≥ 0 korral olgu PDL n +1 PDL alamhulk, milles programmid võivad sisaldada teste A? ainult siis, kui A on PDL n valem. Kõigi n ≥ 0 korral võtsid Berman ja Paterson arvesse PDL n +1 valemi A n +1, mis oli määratletud valemiga
< samas A nei π n > <π n > A n
kus A 0 = p ja π 0 = π ja mis tõestas, et kõigi n ≥ 0 korral puudub PDL n valem, mis oleks samaväärne A n +1-ga. Seega on kõigi n ≥ 0 korral PDL n +1 rohkem väljendusjõudu kui PDL n.
4.2 PDL koos vastupidisega
CPDL on PDL-i laiendamine vastupidisega. See on konstruktsioon, mida on kaalutud PDLi algusest peale. Kõigi programmide α korral laske α -1 semantiliselt uue programmi jaoks
x R (a- 1) y kui y R (a) x.
Vastupidine konstruktsioon võimaldab meil väljendada fakte praegusele riigile eelnenud olekute kohta ja põhjendada programmide mahajäämust. Näiteks [α -1] A tähendab, et enne α täideviimist pidi A hoidma. Meil on
⊨ A → [α] <α -1 > A, ⊨ A → [α -1] A.
Vastupidise konstruktsiooni lisamine ei muuda PDL omadusi olulisel määral. Järgmiste aksioomiskeemide iga eksemplari lisamisega:
(A8) A → [a] <α -1 > A
(A9) A → [α -1] A
PDL-i tõestussüsteemile saame laiendatud keeles kindla ja täieliku mahaarvatavuse predikaadi. Üksikasju leiate Parikhist [1978]. CPDL-il on väikese mudeli omadus ja (CPDL-SAT) on EXPTIME-täielik.
Lihtne on märkida, et CPDL-il on rohkem väljendusjõudu kui PDL-il. Selle nägemiseks kaaluge CPDL valemit <π -1 > 1 ja LTS-sid M = (W, R, V) ja M '= (W', R ', V'), kus W = {x, y}, R (π) = {(x, y)}, W '= {y'}, R '(π) = ∅ ja V (x) = V (y) = V' (y ') = ∅. Kuna M, y sat <π -1 > 1, mitte M ', y' sat <π -1 > 1, ja kuna kõigi PDL valemite A puhul on nii, et M, y sat Affff M ', y' sat A, siis on selge, et ükski PDL valem ei ole võrdne <π -1 > 1.
4.3 PDL kordamise ja silmustega
Kordasime juba jaotises 3.3, tutvustades RPDL-i. Siin võtame kokku rohkem tulemusi RPDL-i ja selle seotuse kohta programmide kordamise mõiste muude variatsioonidega.
RPDL keerukusteooria osas oli Streett [1982] juba tuvastanud, et RPDL-il oli lõplik mudeli omadus; täpselt seda, et iga RPDL-i rahuldav valem A on rahuldatav suuruse mudeli korral, mille pikkus A on maksimaalselt kolmekordne. Automaatteoreetiline argument võimaldas järeldada, et probleemi (RPDL-SAT) saab lahendada deterministliku kolmekordse eksponentsiaalse ajaga (3-EXPTIME). Seega oli otsustamise ülemise piiri (RPDL-SAT) ja otsustamiseks mõeldud lihtsa eksponentsiaalaja alumise piiri (PDL-SAT) vahe avatud. Probleem oli seotud suuresti arvutiteadlaste kasvava huviga ajaloogika ja täpsemalt Kozeni (1983) põhjustatud (ettepanekulise) modaalse μ-kalkulatsiooni (MMC) keerukuse kindlakstegemiseks, kuna RPDL-il on lineaarne löök - üles tõlge MMC-sse. Enamgi veel,Streetti argument lõi mõnevõrra pretsedendi nüüdisaegses automaatehnika kasutamises programmide loogika ja ajalise loogika arvutuslike omaduste tõestamisel. Ajakirjas Vardi ja Stockmeyer [1985] näidati mittedeterministliku eksponentsiaalaja ülemist piiri. Emersonis ja Jutlas [1988] ning selle lõplikul kujul Emersonis ja Jutlas [1999] näidati, et (MMC-SAT) ja (RPDL-SAT) on EXPTIME-täielikud. Kui lisada punkti 4.2 vastassuunaline operaator, saab CRPDL. (CRPDL-SAT) keerukus jäi mõneks aastaks lahtiseks, kuid võib ka näidata, et see on ka EXPTIME-täielik. See saavutatakse Emersoni ja Jutla [1988] ning Vardi [1985], nagu Vardi [1998] tehnikate kombineerimise teel. Ajakirjas Vardi ja Stockmeyer [1985] näidati mittedeterministliku eksponentsiaalaja ülemist piiri. Emersonis ja Jutlas [1988] ning selle lõplikul kujul Emersonis ja Jutlas [1999] näidati, et (MMC-SAT) ja (RPDL-SAT) on EXPTIME-täielikud. Kui lisada punkti 4.2 vastassuunaline operaator, saab CRPDL. (CRPDL-SAT) keerukus jäi mõneks aastaks lahtiseks, kuid võib ka näidata, et see on ka EXPTIME-täielik. See saavutatakse Emersoni ja Jutla [1988] ning Vardi [1985], nagu Vardi [1998] tehnikate kombineerimise teel. Ajakirjas Vardi ja Stockmeyer [1985] näidati mittedeterministliku eksponentsiaalaja ülemist piiri. Emersonis ja Jutlas [1988] ning selle lõplikul kujul Emersonis ja Jutlas [1999] näidati, et (MMC-SAT) ja (RPDL-SAT) on EXPTIME-täielikud. Kui lisada punkti 4.2 vastassuunaline operaator, saab CRPDL. (CRPDL-SAT) keerukus jäi mõneks aastaks lahtiseks, kuid võib ka näidata, et see on ka EXPTIME-täielik. See saavutatakse Emersoni ja Jutla [1988] ning Vardi [1985], nagu Vardi [1998] tehnikate kombineerimise teel.(CRPDL-SAT) keerukus jäi mõneks aastaks lahtiseks, kuid võib ka näidata, et see on ka EXPTIME-täielik. See saavutatakse Emersoni ja Jutla [1988] ning Vardi [1985], nagu Vardi [1998] tehnikate kombineerimise teel.(CRPDL-SAT) keerukus jäi mõneks aastaks lahtiseks, kuid võib ka näidata, et see on ka EXPTIME-täielik. See saavutatakse Emersoni ja Jutla [1988] ning Vardi [1985], nagu Vardi [1998] tehnikate kombineerimise teel.
Punktis 3.3 oleme määratlenud predikaadi ∞, kus ∞ (α) tähendab, et α-l võib olla lõpmatu arvutus. Kutsume LPDL-i loogikaks, mis saadakse PDL-i täiendamisel predikaadiga ment. On selge, et RPDL on vähemalt sama väljendusrikas kui LPDL; Selle tunnistajaks on) (α) induktiivne määratlus RPDL-i keeles. RPDL on tegelikult rangelt väljendusrikkam kui LPDL. Seda näidati ajakirjades Harel ja Sherman [1982]. Nagu võib kahtlustada, on nii RPDL-il kui ka LPDL-il rohkem väljendusjõudu kui PDL-il. See tehakse kindlaks, tõestades, et mõnel RPDL ja LPDL valemil pole PDL-is ekvivalentset avaldist. Tõend hõlmab filtreerimistehnikat, mis on kavandatud LTS-i kokkusurumiseks lõplikuks mudeliks, jättes teatud valemite tõesuse või valede muutumatuse. Mõne PDL valemite komplekti X jaokssee koosneb LTS-i olekute rühmade ekvivalentsusklassidesse grupeerimisest, mis vastavad täpselt samadele valemitele X-is. Sel viisil saadud olekute ekvivalentsusklasside komplektist saab filtraadi mudeli olekute komplekt ja nendele ehitatakse sobiv üleminek.
Hoolikalt valitud komplektiga FL (A), mis sõltub PDL valemist A (nn Fischeri-Ladneri suletus A alamvalemite komplekti sulgemiseks), annab LTS-M filtreerimine piiratud filtraadi M ', näiteks et A on rahul uM-ga maailmas ainult siis, kui see on rahuldatav ekvivalentsusklassis, mis sisaldab u filtraadis. (Vt Fischer ja Ladner [1979].)
Nüüd võime arvestada LTS M = (W, R, V) filtratsiooni kus
W = {(i, j): j ja i positiivsed täisarvud, 0 ≤ j ≤ i} ∪ {u}
(i, j) R (π) (i, j -1), kui 1 <j <i
u R (π) (i, i) iga i kohta
V (p) = ∅ iga p ∈ Φ 0 kohta
Ühes lauses juhtub M-ga see, et maailmast u on lõpmatu arv kasvava pikkusega piiritletud π-radu. Meil on nii M, u sat ¬Δπ kui ka M, u sat ¬∞ (π *). Kuid iga PDL valemi A korral on meil nii Δπ kui ∞ (π *), mis on täidetud u ekvivalentsusklassis mudelis, mis saadakse M filtreerimisel FL (A). Tõepoolest, filtreerimine peab M-i mõned olekud ahendama ja looma mõned silmused. Seega puudub PDL valem, mis väljendaks kas Δπ või ∞ (π *). ja veel, on meil nii Δπ kui ∞ (π *), mis on täidetud ekvivalentsusklassis u mis tahes M filtraadis. Seega ei saa Δπ ega ∞ (π *) väljendada PDL-is.
Väidet, et programm suudab igavesti täita, on ka muid võimalusi. Näiteks Danecki [1984a] ettepanek predikaat sloop saada programmid, mida saab sisestada tugev silmad, mis on:
V (nõlv (α)) = {x: x R (α) x}
Anna meile helistada SLPDL loogika saadud täiendada PDL koos sloop (α). RPDL ja SLPDL on sisuliselt võrreldamatu: predikaat Δ ei ole piiritletav SLPDL ja predikaadi sloop ei ole piiritletav RPDL. SLPDL-il puudub lõpliku mudeli omadus. Näiteks valem
[π *] (1 ∧ ¬ nõlv (π +))
on rahuldatav ainult lõpmatus LTS-is. Sellegipoolest kehtestas Danecki [1984a] (SLPDL-SAT) valemite otsustatavuse deterministliku eksponentsiaalse aja jooksul.
4.4 Ristmiku PDL
Uuritud on veel ühte konstruktsiooni: programmide ristmikku. Programmide ristumise lisamisega PDL-le saame loogika IPDL. IPDL-is tähistab kõigi programmide α, β avaldis α∩β uut semantilisi programme
xR (α∩β) y, kui xR (α) y ja xR (β) y
Näiteks on A kavandatud lugemine selline, et kui täidame α ja β praeguses olekus, siis on olemas mõlemale programmile juurdepääsetav olek, mis vastab A-le. Selle tulemusel oleme
⊨ A → A ∧ A
aga üldiselt meil on
mitte ⊨ A ∧ A → A
Ehkki programmide ristumiskoht mängib olulist rolli PDL-i erinevates rakendustes tehisintellekti ja arvutiteaduse alal, jäeti PDL-i tõestusteooria ja keerukusteooria ristumistega uurimata mitu aastat. IPDL-i keerukusteooria osas ilmnevad raskused, kui arvestada lõpliku mudeli omadust. Tegelikult konstrukt sloop (α) saab väljendada IPDL. Ristmikul pakutavas dünaamilises loogikas võrdub see 1-ga. Seega saame kohandada jaotise 4.3 IPDL-i valemit ja meil on see
[π *] (1 ∧ [π + ∩1?] 0)
on rahuldatav ainult lõpmatus LTS-is. Teisisõnu, IPDL ei oma piiratud mudeli omadust. Danecki [1984b] uuris IPDL-i keerukusteooriat ja näitas, et otsustada (IPDL-SAT) saab teha deterministliku kahekordse eksponentsiaalse aja jooksul. (Kaasaegne tõestusmaterjal on esitatud Gölleris, Lohreys ja Lutzis [2007].) Selle kahekordse eksponentsiaalaja ülemise piiri (IPDL-SAT) ja lihtsa eksponentsiaalaja alumise piiri vahel otsustamiseks (PDL-SAT) on keerukus. mis on saadud Fischeri ja Ladneri poolt [1979], oli avatud enam kui kakskümmend aastat. 2004. aastal kehtestas Lange [2005] (IPDL-SAT) eksponentsiaalse ruumi alumise piiri. 2006. aastalLange ja Lutz [2005] tõestasid IPDL-i rahuldamisprobleemi kahekordse eksponentsiaalaja alumise piiri tõestamata testide abil, vähendades sõna probleemist eksponentsiaalselt kosmosega piiratud vahelduvate Turingi masinate probleemi. Selles redutseerimisel on iteratsioonikonstruktsiooni roll hädavajalik, kuna vastavalt Massacci [2001] andmetele on iteratsioonivaba IPDL-i rahuldamisprobleem ilma testideta ainult PSPACE-täielik. Kui lisada IPDL-ile vastupidine konstruktsioon, saame ICPDL. Göller, Lohrey ja Lutz on tõestanud, et ICPDL-i rahuldatavuse probleem on 2-EXPTIME-täielik. Göller, Lohrey ja Lutz on tõestanud, et ICPDL-i rahuldatavuse probleem on 2-EXPTIME-täielik. Göller, Lohrey ja Lutz on tõestanud, et ICPDL-i rahuldatavuse probleem on 2-EXPTIME-täielik.
IPDL-i tõestusteooria osas ilmnevad raskused, kui mõistame, et ükski aksioomiskeem, ristlõikega PDL-i keeles, "ei vasta" semantidele x R (α∩β) y iff x R (α) y ja x R (β) y programmi α∩β. See tähendab, et mitte näiteks samal viisil, et aksioomiskeemid (A1) ja (A2) vastavad vastavalt programmide α; β ja α∪β semantikale. Sel põhjusel oli PDL ristumiskohtade aksiomatization avatud kuni Balbiani ja Vakarelov [2003] välja töötatud täieliku tõestussüsteemi väljatöötamiseni.
Teises PDL variandis tõlgendatakse Pelegist [1987] tulenevalt ja Goldblatt [1992b] edasi uuritud väljendi α∩β tähendust „do α ja β paralleelselt“. Selles kontekstis ei ole binaarsuhted R (α) ja R (β) enam vormi (x, y) paaride kogumid, millel on x, y maailmad, vaid pigem vormi (x, Y) paaride komplektid xa maailm ja Y maailmade kogum. See oli inspireeritud Parikhi mänguloogikast [1985], PDL-i tõlgendamisest programmidega kui mängudega. Mänguloogika pakub täiendavat programmikonstruktsiooni, mis dubleerib programme, võimaldades seega määratleda programmide ristumiskohta programmidevahelise mittedeterministliku valiku duurina.
5. Järeldus
See artikkel on keskendunud propositsioonilisele dünaamilisele loogikale ja mõnele selle olulisele variandile. Nüüdseks on olemas mitmeid raamatuid - Goldblatt [1982], Goldblatt [1992a], Harel [1979] ja Harel, Kozen ja Tiuryn [2000] ning küsitluslehed - Harel [1984], Kozen ja Tiuryn [1990], Parikh. [1983] - PDL-i ja sellega seotud formalismide käsitlemine. PDL-i uurimistöö on kindlasti abiks paljude süsteemidünaamika loogiliste teooriate väljatöötamisel. Need teooriad jäävad aga vaieldamatult käesoleva artikli reguleerimisalast välja. Van Eijck ja Stokhof [2006] on uuem ülevaade dünaamilist loogikat kasutavatest teemadest, käsitledes erinevaid teemasid, mis pakuvad filosoofidele teatavat huvi: nt kommunikatsiooni dünaamika või loomulik keelesemantika. Viimased raamatud käsitlevad palju üksikasju uuematel teemadel,nagu teadmiste dünaamiline loogika (dünaamiline episteemiline loogika) Van Ditmarschis, Van Der Hoekis ja Kooi [2007] ning pidevate ja hübriidsüsteemide dünaamiline loogika (diferentsiaaldünaamiline loogika) Platzeris [2010]. PDL loodi peamiselt programmide üle arutlemiseks. Programmide arutlemiseks on palju teisigi modaalloogika rakendusi. Algoritmiline loogika on PDL-ile lähemal, kuna see võimaldab programmidest selgesõnaliselt rääkida. Lugejat kutsutakse tutvuma Mirkowska ja Salwicki [1987] uuritud teosega. Ajaline loogika on nüüd teoreetilise arvutiteaduse peamine loogika ja sellel on tihe seos programmide loogikaga. Need võimaldavad väljendada üleminekusüsteemide ajalist käitumist keeltega, mis on siltidest eemal (see tähendab programme). Selle uurimisala aluste ülevaate leiate näiteks Schneiderist [2004].
Bibliograafia
Apt, K., 1981, “Hoare loogika kümme aastat: uuring - I osa”, ACM-i tehingud programmeerimiskeelte ja -süsteemide kohta, 3 (4): 431–483.
Balbiani, P. ja D. Vakarelov, 2003, “PDL programmide ristumiskohas: täielik aksiomatization”, Journal of Applied Non-Classical Logics, 13: 231-276.
van Benthem, J., 1998, “Bisimulatsiooniks ohutud programmikonstruktsioonid”, Studia Logica, 60: 311–330.
Berman, F. ja M. Paterson, 1981, “Propositsiooniline dünaamiline loogika on nõrgem ilma testideta”, Teoreetiline arvutiteadus, 16: 321–328.
Burstall, R., 1974, “Programmi tõestamine kui väikese induktsiooniga käesimulatsioon”, teabetöötlus 74: IFIP kongressi toimetised 74, Amsterdam: Põhja-Hollandi kirjastus, 308–312.
Danecki, R., 1984a, „Propositsiooniline dünaamiline loogika tugeva silmuse predikaadiga”, M. Chytilis ja V. Koubekis, Berliini arvutiteaduse matemaatilised alused: Springer-Verlag, 573–581.
–––, 1984b, „Mittedeterministlik juhendiline dünaamiline loogika ristumistega on otsustatav”, A. Skowron (toim.), Computation Theory, Berliin: Springer-Verlag, 34–53.
De Giacomo, G. ja F. Massacci, 2000, “deduktsiooni ja mudeli kontrollimise ühendamine tabelipõhiseks ja teisendatud PDL-i algoritmideks”, teave ja arvutus, 160: 109–169.
van Ditmarsch, H., W. van Der Hoek ja B. Kooi, 2007, Dynamic epistemic logic, Dordrecht: Springer-Verlag.
van Eijck, J. ja M. Stokhof, 2006, “Dünaamilise loogika spekter”, D. Gabbay ja J. Woods (toim), loogika ajaloo käsiraamat, 7. köide - loogika ja modaalsused Kahekümnes sajand, Amsterdam: Elsevier, 499–600.
Emerson, E. ja Jutla, C., 1988, “Puuautomaatide ja programmide loogika keerukus (laiendatud kokkuvõte)”, 29. iga-aastase arvutiteaduse aluste sümpoosioni toimetustes, Los Alamitos, CA: IEEE Computer Society, 328–337.
–––, 1999, „Puuautomaatide ja programmide loogika keerukus“, SIAM Journal of Computing, 29: 132–158.
Engeler, E., 1967, “Struktuuride algoritmilised omadused”, Mathematical Systems Theory, 1: 183–195.
Fischer, M. ja R. Ladner, 1979, “Regulaarsete programmide proosaline dünaamiline loogika”, Arvuti- ja süsteemiteaduste ajakiri, 18: 194–211.
Floyd, R., 1967, “Programmidele tähenduse omistamine”, American Mathematical Society Symposia on Applied Mathematics (19. köide), Providence, RI: American Mathematical Society, 19–31.
Gargov, G. ja S. Passy, 1988, “Determinism ja silmus kombinatiivses PDL-is”, Teoreetiline arvutiteadus, Amsterdam: Elsevier, 259–277.
Goldblatt, R., 1982, Arvutiprogrammeerimise loogika aksiomaatika, Berliin: Springer-Verlag.
–––, 1992a, aja ja arvutuse loogika, Stanford: Keele ja teabe väljaannete uurimise keskus.
–––, 1992b, “Paralleelne tegevus: samaaegne dünaamiline loogika sõltumatute moodustega”, Studia Logica, 51: 551–578.
Göller, S., M. Lohrey ja C. Lutz, 2007, “Ristumiste ja vastassuhetega PDL on täielik 2EXP-täielik”, Tarkvarateaduse ja arvutusstruktuuride alused, Berliin: Springer, 198–212.
Harel, D., 1979, esimese astme dünaamiline loogika, Berliin: Springer-Verlag.
–––, 1983, “Korduvad doominod: väga otsustamatute ja arusaadavateks muutmine”, M. Karpinski (toim), Arvutusteooria alused, Berliin: Springer-Verlag, 177–194.
–––, 1984, “Dünaamiline loogika”, D. Gabbay ja F. Guenthner (toim), Filosoofilise loogika käsiraamat (II köide), Dordrecht: D. Reidel, 497–604.
Harel, D., D. Kozen ja J. Tiuryn, 2000, Dynamic Logic, Cambridge, MA: MIT Press.
Harel, D. ja Sherman, R., 1982, “Loopimine vs kordamine dünaamilises loogikas”, teave ja kontroll, 55: 175–192.
Kozen, D., 1983, “Propositsionaalse μ-kalkulatsiooni tulemused”, Teoreetiline arvutiteadus, 27: 333–354.
Kozen, D. ja R. Parikh, 1981, “PDL-i täielikkuse tõestamine”, Teoreetiline arvutiteadus, 14: 113–118.
Kozen, D. ja J. Tiuryn, 1990, “Programmide loogika”, J. Van Leeuwen (toim), Teoreetilise arvutiteaduse käsiraamat (B köide), Amsterdam: Elsevier, 789–840.
Lange, M., 2005, “Madalam keerukus, mis on seotud ristlõikega dünaamilise loogikaga”, R. Schmidtis, I. Pratt-Hartmannis, M. Reynoldsis ja H. Wansingis (toim), Advances in Modal Logic (5. köide)), London: King's College Publications, 133–147.
Lange, M. ja C. Lutz, 2005, “2-EXPTIME alumine piir ristlõikega dünaamilise loogika jaoks”, Journal of Symbolic Logic, 70: 1072–1086.
Lutz, C., 2005, “Ristumiste ja vastassuundadega PDL on otsustatav”. L. Ong (toim.), Computer Science Logic, Berliin: Springer-Verlag, 413-427.
Massacci, F., 2001, “Otsustusprotseduurid väljendusrikka loogika kirjeldamiseks koos ristumiste, kompositsiooni, rollide vastandamise ja rolliidentiteediga”, B. Nebel (toim), 17. rahvusvaheline tehisintellekti ühiskonverents, San Francisco: Morgan Kaufmann, 193–198.
Mirkowska, G. ja A. Salwicki, 1987, Algorithmic Logic, Dordrecht: D. Reidel.
–––, 1978, „Praktiline otsustusmeetod dünaamilise loogika jaoks”, ACMi 10. iga-aastase arvutusteooria sümpoosioni kogumikus, New York, NY: ACM, 326–337.
–––, 1980a, “Ligi optimaalne meetod tegevuse põhjendamiseks”, Journal of Computer and System Sciences, 20: 231–254.
–––, 1980b, “Modaalloogika rakendamine programmeerimisel”, Studia Logica, 39: 257–274.
Sakalauskaite, J., ja M. Valiev, 1990, “Jaotusliku dünaamilise loogika täielikkus lõpmatu kordamisega”, P. Petkov (toim.), Mathematical Logic, New York: Plenum Press, 339–349.
Salwicki, A., 1970, “Formaliseeritud algoritmilised keeled”, Bulletin de l'Academie Polonaise des Sciences, Serie des sciences - matemaatika, astronoomia ja füüsika, 18: 227–232.
Segerberg, K., 1977, “Täielikkuse teoreem programmide modaalses loogikas”, Notices of the American Mathematical Society, 24: 522.
Schneider, K., 2004, Reaktiivsete süsteemide kontrollimine, Berliin: Springer-Verlag.
Streett, R., 1982, “Silmusekujulise ja vastupidise alguse dünaamiline loogika on elementaarne otsustatav”, Information and Control, 54: 121–141.
Vakarelov, D., 1983, “Dünaamiliste algebrate filtreerimisteoreem testide ja pöördoperaatoriga”, A. Salwicki (toim.), Programmide ja nende rakenduste loogika, Berliin: Springer-Verlag, 314–324.
Vardi, M. ja Stockmeyer, L., 1985, “Programmide modaalloogika parandatud ülemine ja alumine piir: eelraport”, ACMi 17. iga-aastase arvutusteooria sümpoosioni toimetustes, New York, NY: ACM, 240 –251.
