Propositional Dynamic Logic

Sisällysluettelo:

Propositional Dynamic Logic
Propositional Dynamic Logic

Video: Propositional Dynamic Logic

Video: Propositional Dynamic Logic
Video: Logic for Programmers: Propositional Logic 2024, Maaliskuu
Anonim

Maahantulon navigointi

  • Kilpailun sisältö
  • bibliografia
  • Akateemiset työkalut
  • Ystävät PDF-esikatselu
  • Kirjailija- ja viittaustiedot
  • Takaisin alkuun

Propositional Dynamic Logic

Ensimmäinen julkaisu to 1. helmikuuta 2007; aineellinen tarkistus pe 25. tammikuuta 2019

Ohjelmien logiikka on modaalilogiaa, joka syntyy ajatuksesta assosioida jokaisen ohjelmointikielen α tietokoneohjelmaan modaalisuus [a]. Tämä ajatus perustuu Engelerin [1967], Hoaren [1969], Yanovin [1959] ja muiden teoksiin, jotka ovat muotoilleet ja tutkineet loogisia kieliä, joilla ohjelmaliitosten ominaisuudet voidaan ilmaista. Alkuperäinen logiikka (AL), jonka ensin kehitti Salwicki [1970], ja dynaaminen logiikka (DL), jonka on kehittänyt Pratt [1976], ovat näiden teosten asianmukaisia jatkoksia. Keskitymme tässä DL: ään. Lukuisat DL: lle ja sen muunnelmille omistetut artikkelit sekä sen moninaiset sovellukset ohjelman varmennuksessa ja tietorakenteissa osoittavat, että se on hyödyllinen työkalu ohjelmien ominaisuuksien tutkimiseen. Pratt päätti kuvata DL: n siitä, mitä voidaan kutsua ensimmäisen asteen tasolle,ja hänen työnsä laukaisi Fischerin ja Ladnerin [1979] määrittelemään DL: n ehdotusvariantti muutamaa vuotta myöhemmin. Tässä artikkelissa on johdanto PDL: ään, DL: n ehdotusvarianttiin.

  • 1. Esittely
  • 2. Määritelmät ja perustulokset

    • 2.1 Syntaksi ja semantiikka
    • 2.2 Aksiomatization ja täydellisyys
    • 2.3 Päätettävyys ja monimutkaisuus
  • 3. Jäsennelty ohjelmointi ja ohjelmien oikeellisuus

    • 3.1 Hoare-laskenta
    • 3.2 Hoare-laskenta ja PDL
    • 3.3 Täydellinen oikeellisuus
  • 4. Jotkut vaihtoehdot

    • 4.1 PDL ilman testejä
    • 4.2 PDL käänteisellä
    • 4.3 PDL toistuvilla ja silmukoilla
    • 4.4 PDL risteyksessä
  • 5. Päätelmät
  • bibliografia
  • Akateemiset työkalut
  • Muut Internet-resurssit
  • Aiheeseen liittyvät merkinnät

1. Esittely

Dynaaminen logiikka (DL) on modaalilogiikka, joka edustaa dynaamisten järjestelmien tiloja ja tapahtumia. DL: n kieli on sekä väitekieli, joka kykenee ilmaisemaan laskentatilojen ominaisuudet, että ohjelmointikieli, joka kykenee ilmaisemaan näiden tilojen välisten järjestelmäsiirtymien ominaisuudet. DL: t ovat ohjelmien logiikoita ja sallivat puhua ja pohtia asioiden tilaa, prosesseja, muutoksia ja tuloksia.

Prattin alkuperäinen dynaaminen ohjelmalogiikka oli ensimmäisen asteen modaalilogiaa. Propositional Dynamic Logic (PDL) on sen ehdotuksellinen vastine. Se esitettiin itsenäisenä logiikkana Fischerissä ja Ladnerissa [1979]. Koska ehdotuksellinen, PDL-kieli ei käytä termejä, predikaatioita tai funktioita. Siten PDL: ssä on kaksi syntaktista luokkaa: ehdotukset ja ohjelmat.

Antaaksemme PDL-lauseille merkityksen, työskentelemme tyypillisesti abstraktin semantiikan kanssa merkittyjen siirtymäjärjestelmien (LTS) kannalta. LTS: iä voidaan pitää Kripke-mallien yleistyksenä, jossa siirtymät maailmojen tai valtioiden välillä on”merkitty” atomiohjelmien nimillä. Arviointi osoittaa jokaiselle valtiolle, mitkä ehdotukset ovat totta siinä. Siirtymä, joka on merkitty π yhdestä tilasta x tilaan y - merkitty x R (π) y tai (x, y) ∈ R (π) - osoittaa, että alkaessa x: ssä, mahdollinen ohjelman π suorittaminen päättyy vuonna y Jos lause A on totta y: ssä, niin kaava A on totta x: ssä, eli tilassa x on mahdollista suorittaa ohjelma α, joka päättyy A: n tyydyttävään tilaan. Yksi tunnistaa modaalisuudessa, joka muistuttaa modaalilogiikan mahdollisuuksia (usein merkitty ◊). Ei ole yllättävää,on olemassa myös vastaava käsitys välttämättömyydestä (jonka modaalisuus mainitaan usein □). Kaava [π] A on totta tilassa x, jos A on totta kaikissa tiloissa, jotka ovat saavutettavissa x: stä siirtymämerkinnällä π.

Seuraavaksi voidaan määritellä monimutkaisten ohjelmien mahdolliset suoritukset. Esimerkiksi ohjelma “ensin α, sitten β” on monimutkainen ohjelma, tarkemmin sekvenssi. Mahdollinen suorittaminen voidaan esittää LTS: ssä muodostamalla kaksivaiheinen siirtymä - jolloin siirtymä, joka voidaan merkitä R (α; β) -tilojen x ja x 'välillä: ohjelman mahdollinen suorittaminen tapahtuu x: ssä α, joka päättyy tilassa y ja ohjelmassa β on mahdollista suorittaa suorituskyky y: ssä, joka päättyy x '. Jos lause A on totta x ': ssä, niin kaava A on tosi tilassa x. Ohjelmat α ja β voivat itse olla monimutkaisia ohjelmia. Vielä useampia ohjelmia voidaan ilmaista enemmän konstruktioilla, jotka esittelemme ajoissa.

Ohjelma nähdään sitten laajennuksellisesti: se on binaarinen suhde LTS: n tilaparien välillä. Tarkalleen ottaen se on lomakkeen (x, y) parisarja, joka voi suorittaa ohjelman tilassa x ja johtaa tilaan y. Toisaalta ehdotus on lausunto valtiosta; se on joko totta tai vääriä tilassa. Ehdotus voidaan siten nähdä myös laajennettavalla tavalla: LTS: n tilajoukko, jossa se on totta.

Lyhenteellä PDL viitataan tässä tarkalleen ehdotukselliseen dynaamiseen logiikkaan seuraavilla ohjelmarakenteilla: sekvenssi, ei-deterministinen valinta, rajaton iteraatio ja testi. Esitämme sen osiossa 2 yhdessä eräiden ominaisuuksien ja perusteellisten tulosten kanssa. Käsittelemme erityisesti sen axiomatization ja sen päätöksentekoa.

Hoaren [1969] Hoare-laskenta on maamerkki ohjelmien logiikalle. Se koskee muodon {A} α {B} lausuntojen totuutta - tarkoittaen, että ennakkoedellytyksellä A ohjelmalla α on aina B jälkiedellytyksenä ja se on määritelty aksomaattisesti. Se johtuu siitä, että halutaan tiukat menetelmät pohtia ohjelmien ominaisuuksia ja antaa ohjelmointitoiminnalle tietty sijainti tieteen alueella. Burstall [1974] näki analogian modaalilogiikan ja ohjelmien päättelyn välillä, mutta varsinainen työ sen suhteen alkoi Prattilla [1976], kun R. Moore, hänen tuolloin opiskelija, ehdotti hänelle. PDL tulee Prattin tulkinnasta Hoaren laskennasta modaalilogiikan formalismissa. Johdanto PDL: n syntyyn löytyy julkaisusta Pratt [1980b]. Hoare-kolmio {A} α {B} vangitaan PDL-kaavalla A → [a] B tarkoittaen kirjaimellisesti, että jos A on totta, niin jokainen a: n onnistuneesti lopettava suorittaminen loppuu B: n ollessa totta. Tämän yhteyden toteutuessa on rutiini todistaa Hoaren laskennan alkuperäiset säännöt käyttämällä yksinomaan PDL: n aksiomaatiota. Tätä teemme yksityiskohtaisesti osiossa 3, jossa keskitytään perusteisiin jäsenneltyjen ohjelmien oikeellisuudesta.

Muita PDL: ään liittyviä aiheita ovat tulokset, jotka koskevat ilmaisun vertailuvoimaa, päätettävyyttä, monimutkaisuutta ja täydellisyyttä monille mielenkiintoisille varianteille, jotka on saatu laajentamalla tai rajoittamalla PDL: ää eri tavoin. Alkuvaiheestaan lähtien monet PDL-variantit ovat saaneet huomiota. Nämä vaihtoehdot voivat harkita deterministisiä ohjelmia, rajoitettuja testejä, epäsäännöllisiä ohjelmia, ohjelmia automaatteina, ohjelmien täydentämistä ja leikkaamista, käänteisiä ja äärettömiä laskelmia jne. Esitämme joitain niistä luvussa 4, tarjoamalla joitain osoittimia suhteellisesta ekspressiivisuudestaan, heidän aksioomaationsa ja laskennallisen monimutkaisuutensa.

Johtopäätökset tehdään osiossa 5.

2. Määritelmät ja perustulokset

Esitämme PDL: n syntaksin ja semantiikan osiossa 2.1. PDL: n todisteteoria esitetään osassa 2.2 aksiomaatiot ja osoitteet täydellisyyttä käsittelevään kirjallisuuteen. Käsittelemme päätöksenteko- ja monimutkaisuusongelmaa osassa 2.3.

2.1 Syntaksi ja semantiikka

Propositional Dynamic Logic (PDL) on suunniteltu esittämään ja perustelemaan ohjelmien ehdotusominaisuuksia. Sen syntaksi perustuu kaksi symboleja: numeroituva joukko Φ 0 atomi kaavat ja numeroituva joukko Π 0 atomi ohjelmia. Tämän tukikohdan kompleksiset kaavat ja monimutkaiset ohjelmat määritellään seuraavasti:

  • Jokainen atomikaava on kaava
  • 0 (”väärä”) on kaava
  • Jos A on kaava, niin ¬ A (“ei A”) on kaava
  • Jos A ja B ovat kaavoja, niin (A ∨ B) (“A tai B”) on kaava
  • Jos α on ohjelma ja A on kaava, niin [a] A ("jokainen α: n suorittaminen nykyisestä tilasta johtaa tilaan, jossa A on totta") on kaava
  • Jokainen atomiohjelma on ohjelma
  • Jos α ja β ovat ohjelmia, niin (α; β) (”do α seuraa β”) on ohjelma
  • Jos α ja β ovat ohjelmia, niin (α∪β) (”tee α tai β, ei-deterministisesti”) on ohjelma,
  • Jos α on ohjelma, niin α * (”toista α äärellinen, mutta ei deterministisesti määritetty, kertojen lukumäärä”) on ohjelma.
  • Jos A on kaava, niin A? (“Jatka, jos A on totta, muuten epäonnistuu”) on ohjelma

Muita Boolen liitososia 1, ∧, → ja ↔ käytetään lyhenteinä tavanomaisella tavalla. Lisäksi lyhennämme ¬ [α] ¬ A: sta A: ksi ("jokin a: n suorittaminen nykyisestä tilasta johtaa tilaan, jossa A on totta") kuten modaalilogiikassa. Me kirjoitamme α n α: lle;…; α n: n esiintymällä α: lla. Muodollisemmin:

  • α 0 = df 1?
  • α n +1 = df α; α n

Myös:

α + = df α; α *

on usein hyödyllinen edustamaan iteraatiota, joka ei ole rajaton, mutta tapahtuu ainakin kerran. Lopuksi hyväksymme sulkujen jättämisen vakiosäännöt.

Kaavoja voidaan kuvata ominaisuuksilla, jotka säilyvät ohjelman onnistuneen suorituksen jälkeen. Esimerkiksi, kaava [α∪β] A tarkoittaa, että aina kun ohjelman α tai β suoritetaan onnistuneesti, saavutetaan tila, jossa A pitää, kun taas kaava A tarkoittaa, että α: n ja β: n vuorottelevien toteutusten sekvenssi on sellainen, että a tila saavutetaan missä A pitää. Semanistisesti ottaen kaavat tulkitsevat tilajoukot ja ohjelmat tulkitsevat siirtymäjärjestelmän tilojen binaarisuhteilla. Tarkemmin sanottuna PDL-kaavojen ja -ohjelmien merkitys tulkitaan merkittyjen siirtymäjärjestelmien (LTS) M = (W, R, V) kautta, jossa W on ei-tyhjä maailmojen tai tilojen joukko, R on kuvaus atomin joukosta Π 0 Ohjelmat binaarisuhteiksi W: llä ja V: llä on kartoitus joukosta Φ 0 atomi- kaavojen osa W: n osajoukkoihin.

Epävirallisesti kartoitus R antaa jokaiselle atomiohjelmalle π ∈ Π 0 jonkin binaarisen suhteen R (π) W: llä, jolla on tarkoitus x R (π) y, jos on olemassa π: n suorittaminen arvosta x, joka johtaa y: hen, kun taas kartoitus V antaa jokaiselle atomikaavalle p ∈ Φ 0 jonkin W: n osajoukon V (p) tarkoitetulla merkityksellä x ∈ V (p), jos p on totta x: ssä. Ottaen lukemiamme 0, ¬ A, A ∨ B, [α] A, α; β, α∪β, α * ja A? On selvää, että R: tä ja V: tä on laajennettava induktiivisesti seuraavasti antamaan aiotut merkitykset monimutkaisille ohjelmille ja kaavoille:

  • x R (α; β) y, jos on olemassa maailma z sellainen, että x R (α) z ja z R (β) y
  • xR (aβ) y x x R (a) y tai x R (β) y
  • x R (α *) y, jos olemassa ei-negatiivinen kokonaisluku n ja olemassa maailmoja z 0,…, z n siten, että z 0  = x, z n  = y ja kaikille k = 1.. n, z k −1 R (a) z k
  • x R (A?) y, jos x = y ja y ∈ V (A)
  • V (0) = ∅
  • V (¬ A) = W / V (A)
  • V (A ∨ B) = V (A) ∪ V (B),
  • V ([α] A) = {x: kaikille maailmoille y, jos x R (α) y sitten y ∈ V (A)}

Jos x ∈ V (A), sanomme, että A on tyytyväinen tilassa x M: ssä tai “M, x sat A”.

Kaksi kaksisuuntaista LTS: tä
Kaksi kaksisuuntaista LTS: tä

Soita M: lle vasemmalla olevalle yllä olevalle LTS: lle ja oikealle M 'LTS: lle. Muodollisesti määriteltynä meillä on M = (W, R, V) 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 meillä on M '= (W', R ', V') 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 }. Meillä on esimerkiksi:

  • M, x 1 sat p
  • M, x 2 sat
  • M, x 1 sat <π 1 > p ∧ <π 2 > q
  • M, x 1 sat [π 1] p ∧ [π 1 *] p
  • M ', y 1 sat << 1 *; π 2 > q
  • M', y 2 sat [π 1 *] p
  • M ', y 1 sat [π 1 ∪π 2] (q ∨ p)
  • M ', y 3 sat [π 1 ∪π 2] 0

Mieti nyt kaavaa A. Sanomme, että A pätee M: ssä tai että M on mallin A tai “M ⊨ A”, esimerkiksi kaikille maailmoille x, x ∈ V (A). A: n sanotaan olevan voimassa tai”“A”, jos kaikissa malleissa M, M ⊨ A. Sanomme, että A on tyydyttävissä M: ssä tai että M tyydyttää A: n tai “M sat A”, jos on olemassa maailma x sellainen, että x ∈ V (A). A: n sanotaan olevan tyydyttävää tai”sat A”, jos on olemassa malli M sellainen, että M sat A. Mielenkiintoista,

sat Aff, ei ⊨ ¬ A

⊨ Aff, ei sat ¬ A

Jotkut merkittävät PDL-kaavat ovat kelvollisia. (Lukija voi yrittää todistaa ne muodollisesti tai ainakin alkaa vakuuttaa itsensä yllä esitetyistä harvoista esimerkeistä.)

⊨ [α; β] A ↔ [α] [β] A

⊨ [α∪β] A ↔ [α] A ∧ [β] A

⊨ [α *] A ↔ A ∧ [α] [α *] A

⊨ [A?] B ↔ (A → B)

Vastaavasti voimme kirjoittaa ne kaksoismuodossaan.

A ↔ A

⊨ A ↔ A ∨ A

⊨ A ↔ A ∨ A

⊨ <A?> B ↔ A ∧ B

Yksi mielenkiintoinen käsite koskee PDL-kaavoilla ilmaistun tiedon määrää, joka sisältyy LTS: ään. LTS: ksi kuvatun järjestelmän käyttäytyminen onkin muodossaan todellakin hiukan piilotettu. Esimerkiksi yksinkertaisella tarkastuksella on helppo vakuuttaa itse, että kahdella yllä kuvatulla LTS: llä on sama käyttäytyminen ja että ne täyttävät samat PDL-kaavat. Tämän syntaksin ja semantiikan osan loppuun saattamiseksi annamme näiden väitteiden teoreettisen perustan.

Kun otetaan huomioon kaksi LTS: ää, voidaan kysyä, täyttävätkö ne samat kaavat. Bisimulaation käsitteestä on tullut standardimitta Kripken mallien ja merkittyjen siirtymäjärjestelmien vastaavuudelle. Bisimulaatio LTS: n M = (W, R, V) ja M '= (W', R ', V') välillä on binäärinen suhde Z niiden tilojen välillä siten, että kaikille maailmoille x M: ssä ja kaikille maailmoille x ' M: ssä, jos xZx 'sitten

  • kaikille atomikaavoille p ∈ Φ 0, x ∈ V (p) iff x '∈ V' (p)
  • kaikille atomiohjelmille π ∈ Π 0 ja kaikille y: n maailmoille M: ssä, jos x R (π) y, niin M: ssä on maailma y 'sellainen, että yZy' ja x 'R' (π) y '
  • kaikille atomiohjelmille π ∈ Π 0 ja kaikille maailmoille y 'M: ssä, jos x' R '(π) y', niin M: ssä on maailma y siten, että yZy 'ja x R (π) y

Sanomme, että kaksi LTS: ää ovat samanarvoisia, kun niiden välillä on bisimulaatio. PDL: n alusta lähtien on ollut tiedossa, että kahdessa kaksisuuntaisessa LTS: ssä M ja M ', kaikissa maailmoissa x M: ssä ja kaikissa maailmoissa x' M: ssä, jos xZx ', niin kaikissa PDL-kaavoissa A, x ∈ V (A) iff x '∈ V' (A). Siten, kun kaksi LTS: ää ovat bisimulaarisia edellä olevan bisimulaation määritelmän mukaisesti, on totta, että jos xZx '

  • kaikille ohjelmille α ja kaikille maailmoille y M: ssä, jos x R (α) y, niin maailmassa y on M: ssä sellainen, että yZy 'ja x' R '(α) y'
  • kaikille ohjelmille α ja kaikille maailmoille y 'M: ssä, jos x' R '(α) y', niin M: ssä on maailma y siten, että yZy 'ja x R (α) y

Siksi voidaan yksinkertaisesti vertailla kahden LTS: n käyttäytymistä tarkistamalla vain atomiohjelmat ja ekstrapoloimalla turvallisesti näiden LTS: ien vertailukäyttäytyminen jopa monimutkaisten ohjelmien osalta. Sanomme, että PDL: n ohjelmarakenteet ovat turvallisia bisimulaatiolle. Katso Van Benthem [1998] tarkat karakterisoinnit ohjelmakonstruktioille, jotka ovat turvallisia bisimulaatiolle.

On helposti nähtävissä, että kaksi edellä mainittua LTS: n tapausta ovat samanarvoisia. Bisimulaatio Z välillä M ja M 'voidaan esittää seuraavasti: Z = {(x 1, y 1), (x 1, y 2), (x 2, y 3), (x 2, y 4)}. Tila x 1 ja y 1 täyttävät täsmälleen samat PDL-kaavat. Joten tee tilat x 1 ja y 2 jne.

2.2 Aksiomatization ja täydellisyys

Todisteteorian tarkoituksena on antaa ominaisuuden ⊨ A karakterisointi aksioomien ja päätelmissääntöjen suhteen. Tässä jaksossa määrittelemme vähennyskelpoisuuden predikaatin ⊢ induktiivisesti kaavojen operaatioilla, jotka riippuvat vain niiden syntaktisesta rakenteesta siten, että kaikille kaavoille A,

Aff ⊨ A.

Tietenkin, PDL on jatko klassiselle ehdotuslogiikalle. Odotamme ensin, että kaikki väitteelliset tautologiat pysyvät voimassa, ja kaikki ehdotuspäätelmät ovat sallittuja. Erityisesti modus ponens on voimassa oleva sääntö: A: sta ja A: sta → B päättelevät B: stä. Minkä tahansa ohjelman α kohdalla, rajoittamalla LTS suhteeseen R (α), saadaan Kripke-malli, jossa modaalisuuden logiikka [a] on heikoin ehdotuksellinen normaalimodaalinen logiikka, nimittäin logiikka K. Näin ollen PDL sisältää kaikki esiintymät tutusta jakeluaksiaaliohjelmasta:

(A0) [α] (A → B) → ([α] A → [α] B)

ja se on suljettu seuraavan päätelmissäännön perusteella (välttämättömyyssääntö):

(N) A: sta [a] A: sta.

Modaalilogiikka on normaalia, jos se noudattaa (A0) ja (N). Tärkeitä ominaisuuksia kaikille a: lle ovat, että [a] jakautuu konjunktioon ∧, ja monotonisuuden sääntö, joka sallii A → B: stä päätellä [a] A → [a] B, voidaan todistaa. Lopuksi, PDL on vähiten normaali modaalilogiikka, joka sisältää jokaisen seuraavien aksioomikaavioiden esiintymät

(A1) [α; β] A ↔ [α] [β] A

(A2) [α∪β] A ↔ [α] A ∧ [β] A

(A3) [α *] A ↔ A ∧ [α] [a *] A

(A4) [A?] B ↔ (A → B)

ja suljettu seuraavan päätelmissäännön mukaisesti (silmukan invarianssisääntö):

(I) kohdasta A → [α] A päättely A → [a *] A

Jos X on kaavajoukko ja A on kaava, sanotaan, että A on ⊢-deduktiivinen X: stä, tai “X ⊢ A”, jos on olemassa sekvenssi A 0, A 1,…, A n kaavoista, jotka n  = A ja kaikille i ≤ n A i on esimerkki selviö skeema, tai kaavan X, tai se tulee aikaisemmin kaavat sekvenssin sääntö päättely. Lisäksi: i Aff ∅ ⊢ A; tässä tapauksessa sanomme, että A on ⊢-deduktiivinen. X: n sanotaan olevan consistent-johdonmukainen, jollei X ⊢ 0. On helppo todeta, että (I) voidaan korvata seuraavalla aksioomikaaviolla (induktion aksioomikaavio):

(A5) [α *] (A → [α] A) → (A → [α *] A)

Ensin todetaan, että (I) on johdettu todistusjärjestelmän sääntö, joka perustuu (A1), (A2), (A3), (A4) ja (A5):

1. A → [a] A lähtökohta
2. [a *] (A → [a] A) alkaen 1 käyttäen (N)
3. [α *] (A → [α] A) → (A → [α *] A) aksioomikaavio (A5)
4. A → [a *] A välillä 2 ja 3 modus ponenilla

Otetaan seuraavaksi, että (A5) on ⊢-deduktiivinen:

1. [α *] (A → [α] A) ↔ (A → [α] A) ∧ [α] [α *] (A → [α] A) aksioomikaavio (A3)
2. A ∧ [α *] (A → [α] A) → [α] (A ∧ [α *] (A → [α] A)) yhdestä 1 käyttämällä ehdotusperusteita ja [a]: n jakautumista yli ∧
3. A ∧ [α *] (A → [α] A) → [α *] (A ∧ [α *] (A → [α] A)) alkaen 2 käyttämällä (I)
4. [α *] (A → [α] A) → (A → [α *] A) 3: sta käyttämällä ehdotusperusteita ja [α *]: n jakautumista yli ∧

PDL: n aksiomaatiota aksioomikaavioiden (A1), (A2), (A3), (A4) ja (A5) perusteella on ehdotettu Segerbergissä [1977]. Edellä esitetyistä määritelmistä seuraa, että ⊢ on vakaa suhteessa ⊨: een, ts

Kaikille kaavoille A, jos ⊢ A, niin ⊨ A

Todistus etenee induktiolla A: n vähennyspituuden suhteen ⊢. Kysymys ⊢: n täydellisyydestä suhteessa ⊨, ts.

Kaikille kaavoille A, jos ⊨ A, niin ⊢ A

useita logiikkoja jatkoi. Segerbergissa [1977] esitetty päättely oli ensimmäinen yritys todistaa ⊢: n täydellisyys. Pian Parikh keksi myös todisteen. Kun vuoden 1978 alkupuolella Segerberg löysi virheensä väitteissään (jonka hän lopulta korjasi), Parikh julkaisi mitä voidaan pitää ensimmäisenä todisteena ⊢: n täydellisyydestä Parikhissa [1978]. Vuodesta lähtien on julkaistu erilaisia todisteita ⊢: n täydellisyydestä, esimerkiksi Kozen ja Parikh [1981].

Lisäksi on etsitty erilaisia vaihtoehtoisia PDL-todiste teorioita. Jo varhain, etenkin Prattissa [1978]. Mainitaan sitten myös Nishimuran [1979] ja Vakarelovin [1983] siihen liittyvien teorioiden täydellisyys.

Vaihtoehtoinen formulaatio päästövähennyspredikaatista PDL: lle sallii epäsivun päätelmissäännön käytön, kuten esimerkiksi Goldblattissa [1992a]. (Epätyypillinen päätelmissääntö vie ääretön määrän tiloja.) Olkoon ⊢ 'vähennyskelpoisuuslause, joka vastaa ehdotuksen dynaamisen logiikan kielellä vähiten normaaliin modaalilogiaan, joka sisältää kaikki aksioomikaavioiden (A1), (A2) esimerkit, (A3) ja (A4) ja suljetaan seuraavien infinitaaristen päätelmien mukaisesti:

(I ') ryhmästä {[β] [α n] A: n ≥ 0} päätellä [β] [α *] A

Voidaan todistaa, että ⊢ 'on sekä vakaa että täydellinen suhteessa ⊨, ts.

Kaikille kaavoille A, i 'iff ⊨ A

Toisin sanoen kaikkien voimassa olevien kaavojen joukon generoimiseksi todistusjärjestelmät ⊢ ja ⊢ 'ovat vastaavat.

2.3 Päätettävyys ja monimutkaisuus

Monimutkaisusteorian tarkoituksena on selvittää sat A: n ominaisuuden laskettavuus ajan tai tilan resurssien suhteen. Loogisen L monimutkaisuus tunnistetaan usein ongelmasta päättää sen kaavojen tyydyttävyys, joka määritellään seuraavasti:

(L-SAT) Kun kaava L on L, onko A tyydyttävä?

Tässä osassa tutkimme seuraavan päätöksentekoon liittyvän ongelman monimutkaisuutta:

(PDL-SAT) Kun otetaan huomioon PDL: n kaava A, onko A tyydyttävä?

PDL: n täydellinen aksiomatizisaatio on rekursiivinen määritelmä voimassa olevista PDL-kaavoista, tai toisin sanoen kaavojen joukosta, jonka kieltäminen ei ole tyydyttävää. Siksi ongelman (PDL-SAT) suhteen meillä on alamenettely, joka vastaisi kieltävästi, jos PDL-kaava A ei olisi tyydyttävä. Alaproseduuri (SP1) koostuu kaikkien kaavojen ⊢-johdettavissa olevien numeroinnista, aloittaen aksioomista ja päätelmällä muista lauseista päätelmissääntöjen avulla. Jos kaava on ⊢-deduktiivinen, riittävästi aikaa annettaessa alamenettely löytää sen lopulta. Siten, jos A ei ole tyydyttävä, (SP1) on lopulta löydettävä ¬ A ja vastattava “ei”, kun se tapahtuu.

Jos kaava A on kuitenkin tyydyttävä, niin (SP1) ei koskaan löydä ¬ A: ta. Se toimisi ikuisesti, ja siitä ei voinut olla varma milloin tahansa. Mutta tästä epävarmuudesta on olemassa tapa. Voimme myös ajatella toista alamenettelyä, joka vastaa”kyllä”, jos PDL-kaava on tyydyttävä. Yksi varhaisimmista tuloksista PDL: llä oli todiste siitä, että PDL: llä on äärellinen malliominaisuus, ts.

Kaikille kaavoille A, jos sat A, on olemassa äärellinen malli M sellainen, että M sat A.

Äärellinen malliominaisuus tarjoaa perustan alaproseduurille (SP2), joka koostuu luetellaan yksitellen PDL: n äärelliset mallit ja testataan, täyttääkö yksi niistä kaavan. (Kaikille kaavoille A ja kaikille äärellisille malleille M on helppo testata, onko M sat A soveltamalla määritelmää V (A).) Siten, jos A on tyydyttävä, sen on lopulta löydettävä malli M sellaiseksi, että M sat A ja vastaa “kyllä”, kun se tapahtuu. Symmetrisesti ensimmäiseen alamenettelyyn (SP1), jos kaava A ei ole tyydyttävä, niin (SP2) ei koskaan löydä sitä tyydyttävää mallia, se toimii ikuisesti, ja siitä ei voinut olla varma milloin tahansa.

Yhdistämällä (SP1) ja (SP2) yhdessä, meillä on tapa päättää, onko PDL-kaava A tyydyttävä. Riittää, kun ajaa niitä rinnakkain: jos A on tyydytettävä, (SP2) vastaa lopulta”kyllä”, jos A ei tyydytä, niin (SP1) vastaa lopulta “ei”. Menettely keskeytyy, kun joko (SP1) tai (SP2) antaa vastauksen.

Jos saatu menetelmä riittää päätelmään, että ongelma (PDL-SAT) on ratkaistavissa, se on käytännössä erittäin tehoton. Tuloksena on Fischerin ja Ladnerin [1979] sekä Kozenin ja Parikhin [1981] ansiosta - vahvempi kuin äärellinen malliominaisuus, joka on pieni malliominaisuus:

Kaikille kaavoille A, jos sat A, on olemassa äärellinen malli M, jonka koko on eksponentiaalinen A: ssa M siten, että M sat A.

Tämä tarkoittaa, että me nyt tiedämme, milloin lopettaa kaavan tyydyttävän mallin etsiminen menettelyssä (SP2). Siksi voimme (SP2): lla testata, onko kaava tyydyttävä, mutta kun olemme käyttäneet kaikki pienet mallit, voimme päätellä, että kaava ei ole tyydyttävä. Tämä tuottaa proseduurin, joka suoritetaan epädeterministisesti eksponentiaalisessa ajassa (NEXPTIME): Arvaa malli, jonka koko on korkeintaan yksittäisesti eksponentiaalinen, ja tarkista, täyttääkö se kaavan. Mutta PDL: n monimutkaisusteorian avaintulokset ovat peräisin Fischeriltä ja Ladnerilta [1979] ja Prattilta [1980a]. Havaittuaan, että PDL-kaava voi kuvata tehokkaasti lineaarisesti avaruusrajoitetun vaihtuvan Turingin koneen laskennan, Fischer ja Ladner [1979] määrittelivät ensin (PDL-SAT) eksponentiaalisen ajan alarajan. (PDL-SAT) EXPTIME-yläraja on saatu Prattilta [1980a],joka käytti taulukkokäsittelymenetelmän PDL-ekvivalenttia. Siten (PDL-SAT) on EXPTIME-täydellinen. (Käytännössä tehokkaampaa algoritmia, vaikka se edelleen toimii deterministisellä eksponentiaalisella ajanjaksolla pahimmassa tapauksessa, ehdotetaan julkaisuissa De Giacomo ja Massacci [2000].)

3. Jäsennelty ohjelmointi ja ohjelmien oikeellisuus

Historiallisesti ohjelmien logiikka johtuu 1960-luvun lopun tietokonetekijöiden työstä, jotka olivat kiinnostuneita antamaan merkitys ohjelmointikielelle ja löytämään tiukat standardit ohjelmien todisteille. Tällaiset todisteet voivat olla esimerkiksi ohjelman oikeellisuudesta suhteessa odotettuun käyttäytymiseen tai ohjelman lopettamiseen. Peruslehti on Floyd [1967], joka esittää rakenteellisten tietokoneohjelmien ominaisuuksien analyysin vuokaavioita käyttämällä. Jotkut varhaiset työt, kuten Yanov [1959] tai Engeler [1967], olivat edistyneet ja opiskelleet muodollisia kieliä, joilla ohjelmaliitosten ominaisuudet voidaan ilmaista. Hoaren [1969] muodollisuus oli virstanpylväs PDL: n tulossa. Sitä ehdotettiin Floydin vuokaavioiden tiukka aksioomaattisena tulkintana. Puhumme usein Hoare-logiikasta tai Floyd-Hoare-logiikasta,tai Hoare calculus, kun viitataan tähän muodollisuuteen. Hoare calculus käsittelee lauseiden totuutta (”Hoare triples”), kuten {A} α {B}, joka muodostaa yhteyden ehdollisuuden A, ohjelman α ja jälkitilanteen B välillä. Se osoittaa, että aina kun A on ennakkoedellytys α: n suorittamiselle, niin B pidetään jälkiehtona α: n onnistuneen suorittamisen jälkeen.

Se oli totta jo vuosikymmeniä sitten, ja on edelleenkin: ohjelman validointi tapahtuu useimmiten kuin ei testattamalla sitä kohtuullisella erilaisilla syötteillä. Jos tulo ei tuota odotettua tulosta, "vika" korjataan. Jos lopulta jokaisesta testatusta sisääntulosta saamme odotetun tuloksen, voidaan uskoa, että ohjelmassa ei ole virhettä. Tämä on kuitenkin aikaa vievä validointimenetelmä, ja se jättää tilaa testaamattomille syötteille, jotka epäonnistuvat. Näiden virheiden löytäminen ohjelman käyttöönoton ja käytön jälkeen on resursseista vielä kalliimpaa. Ohjelmien oikeellisuuden perustelu muodollisilla menetelmillä on kriittisten järjestelmien kannalta ratkaisevan tärkeää, koska se tarjoaa tavan todistaa tyhjentävästi, että ohjelmassa ei ole virheitä.

3.1 Hoare-laskenta

Hoare-laskennassa olevien sääntöjen kaappaamien ohjelmien eräänlaisten periaatteiden havainnollistamiseksi riittää, että käydään läpi joitain niistä. (Huomaa: säännöt tarkoittavat, että jos kaikki rivin yläpuolella olevat lausunnot pitävät kiinni tiloista - niin myös rivin alla olevassa lausunnossa - päätelmät pätevät.)

{A} α 1 {B} {B} α 2 {C} (kokoonpanosääntö)
{A} a 1; α 2 {C}

Sävellysääntö kaappaa ohjelmien perus- ja peräkkäisen koostumuksen. Tilanteina meillä on kaksi olettamusta kahden ohjelman α 1 ja α 2 osittaisesta oikeellisuudesta. Ensimmäinen oletus on, että kun a 1 suoritetaan tilassa, joka tyydyttää A: n, niin se loppuu tilaan, joka tyydyttää B: n, aina kun se pysähtyy. Toinen oletus on, että kun α 2 on toteutettu tilassa täyttävän B, sitten se päättyy tilaan täyttävän C, kun se pysähtyy. Säännön päätelmä koskee ohjelman α 1; α 2 osittaista oikeellisuutta (eli α 1, joka koostuu peräkkäin α 2: n kanssa)), joka seuraa kahdesta oletuksesta. Nimittäin, voimme päätellä, että jos α 1, α 2 suoritetaan tilassa täyttävät A, sitten se päättyy tilaan täyttävän C, kun se pysähtyy.

Iteraatiosääntö on tärkeä, koska se kaappaa ohjelmien olennaisen kyvyn suorittaa jotakin koodin osaa toistuvasti, kunnes tietty tila lakkaa pitämästä voimassa.

{A ∧ B} α {A} (iteraatiosääntö)
{A}, kun taas B tekee α {¬ B ∧ A}

Lopuksi, kaksi seuraamussääntöä ovat olennaisen tärkeitä, jotta muodolliselle perustalle voidaan antaa intuitiivisesti selkeät päättelyt, joihin liittyy heikommat jälkitilanteet ja vahvemmat edellytykset.

{A} α {B} B → C (seuraussääntö 1)
{A} α {C}
C → A {A} α {B} (seuraussääntö 2)
{C} α {B}

Hoare [1969]: n esittämässä muodollisuudessa jätämme sen aksioomikaavion pois, koska se vaatisi ensimmäisen kertaluvun kieltä. Lopuksi, myöhemmässä Hoare-logiikan työssä lisätään usein myös enemmän sääntöjä. Katso Apt [1979] aikaisesta katsauksesta.

3.2 Hoare-laskenta ja PDL

Dynaaminen logiikka tulee Prattin tulkinnasta Hoare-kolmoista ja Hoare calculuksesta modaalilogiikan formalismissa. Modaalisuudella [α] voimme muodollisesti ilmaista, että kaikki tilat, jotka ovat saavutettavissa suorittamalla α, täyttävät kaavan A. Tämä tehdään kirjoittamalla [a] A. Siten Hoare-kolmio {A} α {B} otetaan yksinkertaisesti PDL-kaavalla

A → [a] B

Lisäksi tärkeät ohjelmointirakenteet tuodaan helposti PDL: ään määrittelevän lyhenteen avulla:

  • jos A, sitten α muu β = df ((A?; α) ∪ (¬ A?; β))
  • kun taas A do α = df ((A ?; a) *; ¬ A?)
  • toista α, kunnes A = df (α; ((¬ A; α) *; A?))
  • keskeyttää = df 0?
  • ohita = df 1?

Siten näyttää siltä, että PDL: llä meillä on hyvät valmiudet todistaa loogisesti jäsenneltyjen ohjelmien oikeellisuus. Tämän PDL: n ja Hoare calculuksen välisen melko käsin heiluttavan yhteyden lisäksi ei ehkä ole vielä selvää, kuinka ne liittyvät muodollisesti. PDL on itse asiassa Hoare-laskennan yleistys siinä mielessä, että kaikki Hoare-laskennan säännöt voidaan todistaa PDL: n aksomaattisessa järjestelmässä. (Tarkkaan ottaen, Hoare-laskenta sisältää aksioomeja, jotka edellyttävät ensimmäisen asteen dynaamisen logiikan laajennettua kieltä.) Tämä on melko huomattavaa, joten osoitamme tässä kaksi edellä mainittua sääntöä toimimaan esimerkkeinä.

Todisteet alkavat olettamalla sääntöjen lähtökohdat. Sitten käyttämällä näitä oletuksia, aksioomeja ja PDL-sääntöjä, eikä mitään muuta, tavoitteena on varmistaa, että sääntöjen päätelmät seuraavat loogisesti. Siksi koostumussääntöä varten aloitamme olettamalla {A} α 1 {B}, joka on A → [α 1] B sen PDL-formulaatiossa, ja olettamalla {B} α 2 {C}, joka on B → [a 2] C. Tavoitteena on todistaa, että {A} α 1; α 2 {C}. Tarkalleen ottaen haluamme todeta, että A → [α 1; α 2] C on ⊢-deduktiivinen kaavojen joukosta {A → [α 1] B, B → [α 2] C}.

1. A → [a 1] B oletus {A} α 1 {B}
2. B → [a 2] C oletus {B} α 2 {C}
3. [a 1] B → [a 1] [a 2] C 2: sta käyttäen [a 1]: n monotoniaa
4. A → [a 1] [a 2] C välillä 1 ja 3 käyttämällä ehdotusperusteita
5. [a 1; a 2] C ↔ [a 1] [a 2] C aksioomikaavio (A1)
6. A → [α 1; α 2] C välillä 4 ja 5 käyttämällä ehdotusperusteita
- {A} α 1; α 2 {C}

Toisto iteraation säännöstä on hieman enemmän mukana.

1. A ∧ B → [α] A oletus {A ∧ B} α {A}
2. A → (B → [a] A) alkaen 1 käyttämällä ehdotuspäättelyä
3. [B?] [A] A ↔ (B → [a] A) aksioomikaavio (A4)
4. A → [B?] [A] A välillä 2 ja 3 käyttämällä ehdotusperusteita
5. [B?; a] A ↔ [B?] [a] A aksioomikaavio (A1)
6. A → [B?; A] A välillä 4 ja 5 käyttämällä ehdotusperusteita
7. A → [(B?; A) *] A alkaen 6 käyttämällä (I)
8. A → (¬ B → (¬ B ∧ A)) ehdotuksellinen tautologia
9. A → [(B?; Α) *] (¬ B → (¬ B ∧ A)) välillä 7 ja 8 käyttämällä [(B?; a) *]: n monotoniaa ja ehdotuspäättelyä
10. [¬ B?] (¬ B ∧ A) ↔ (¬ B → (¬ B ∧ A)) Aksiomikaavio (A4)
11. A → [(B?; A) *] [¬B?] (¬B ∧ A) 9 ja 10 käyttämällä [(B?; a) *]: n monotoniaa ja ehdotuspäättelyä
12. [(B?; A) *; ¬B?] (¬B ∧ A) ↔ [(B?; Α) *] [¬B?] (¬B ∧ A) aksioomikaavio (A1)
13. A → [(B?; A) *; ¬B?] (¬B ∧ A) alkaen 12 käyttämällä ehdotuspäättelyä
- {A}, kun taas B tekee α {¬ B ∧ A}

PDL: n yhteydessä nämä kaksi seuraamussääntöä ovat itse asiassa koostumussäännön erityistapaukset. Saada ensimmäinen sääntö, korvata α 1 kanssa α ja α 2 kanssa ohittaa. Saamiseksi toisen säännön korvata α 1 kanssa ohittaa ja α 2 kanssa α. Riittää, kun sovelletaan aksioomikaaviota (A4) ja huomautetaan, että [α; ohita] A ↔ [a] A ja [a; ohita] A ↔ [α] A ovat myös ⊢-deduktiiviset kaikille A ja kaikille α.

3.3 Täydellinen oikeellisuus

Hoaren omalla tunnustuksella Hoareen [1979] hänen alkuperäinen laskenta oli vain lähtökohta ja kärsi melkoisista rajoituksista. Erityisesti se antaa vain yhden perustella osittaisesta oikeellisuudesta. Toisin sanoen lauseen {A} α {B} totuus varmistaa vain, että kaikki α: n teloitukset, jotka alkavat A: ta tyydyttävässä tilassa, päättyvät B: tä tyydyttävään tilaan tai eivät pysähdy. Toisin sanoen osittain oikeassa ohjelmassa voi olla loppumattomia suorituksia. (Itse asiassa ohjelma, jolla ei ole päättävää suoritusta, on aina osittain oikein. Näin on esimerkiksi ohjelmassa, kun 1 ohitetaan. Kaava A → [ kun 1 ohitetaan] B on johdettavissa kaikille kaavoille A ja B.) Laskenta ei tarjoa perustaa todisteille ohjelman päättymisestä. Sitä voidaan muokata ottamaan huomioon ohjelmien täydellinen oikeellisuus: osittainen oikeellisuus plus lopetus. Se saavutetaan muuttamalla iteraatiosääntöä. Emme esitä sitä täällä ja viittaavat kiinnostuneeseen lukijaan Apt: iin [1981].

Ensin huomataan, että deterministisissä ohjelmissa voidaan jo kaappaa täydellinen oikeellisuus tällaisten kaavojen avulla

A → B

Lauseke B tarkoittaa, että on olemassa a: n suorittaminen, joka päättyy tilassa, joka tyydyttää B: n. Lisäksi, jos a on deterministinen, tämä mahdollinen lopettava suorittaminen on a: n ainutlaatuinen suorittaminen. Siten, jos joku ensin voi todistaa ohjelman olevan deterministinen, tämä temppu toimii riittävän hyvin todistaakseen sen täydellisen oikeellisuuden.

PDL-alueella on yleinen ratkaisu täydellisen oikeellisuuden ongelmaan. Mutta meidän on laajennettava sitä hiukan. Pratt oli jo viitannut Prattissä [1980b], että PDL ei ole riittävän ilmeikäs tarttumaan ohjelmien äärettömään silmukkaan. Reaktiossa Streett [1982] lisäsi toistuvan PDL: n (RPDL). Se sisältää kaikille ohjelmille α lausekkeen Δα, joka tarkoittaa uutta semantiikkaehdotusta

V (αα) = {x: on olemassa ääretön sekvenssi x 0, x 1,… tiloista siten, että x 0  = x ja kaikille n ≥ 0, x n R (α) x n +1 }

Streett [1982] arvioi, että RPDL voidaan aksiomatoida lisäämällä PDL: n todistusjärjestelmään tarkalleen seuraavat aksioomikaaviot.

(A6) αα → Δα

(A7) [α *] (A → A) → (A → αα)

Arviointi todistettiin Sakalauskaite ja Valiev [1990]. (Yhdistelmä-PDL-version variantin oletusversio todistettiin myös Gargovissa ja Passyssä [1988].)

On helppo nähdä, että yllä esitetyssä Hoare-laskutoimituksessa lopettamisen estäminen voi johtua vain iterointisäännöstä. Analogisesti PDL-ohjelman lopettamatta jättäminen voi johtua vain rajattoman iteroinnin käytöstä. Lauseke Δα osoittaa, että α * voi poiketa toisistaan, ja tämä on juuri sellainen käsitys, jota tarvitsemme. Voimme nyt induktiivisesti määritellä predikaatin ∞ siten, että ohjelmalle α kaava ∞ (α) on totta tarkalleen silloin, kun α voi syöttää loppumattoman laskennan.

∞ (π): = 0 missä π ∈ Π 0

∞ (φ?): = 0

∞ (α ∪ β): = ∞ (α) ∨ ∞ (β)

∞ (α; β): = ∞ (α) ∨ ∞ (β)

∞ (α *): = Δα ∨ ∞ (α)

Lopuksi ohjelman täydellinen oikeellisuus voidaan ilmaista tyyppisillä kaavoilla

A → (¬∞ (α) ∧ [α] B)

mikä tarkoittaa kirjaimellisesti, että jos kyse on A, niin ohjelma α ei voi ajaa ikuisesti ja jokainen onnistunut suorittaminen loppuu tilaan, joka tyydyttää B: n.

4. Jotkut vaihtoehdot

Useiden PDL-varianttien ilmaisun vertailuvoimaa, päätettävyyttä, monimutkaisuutta, aksiomaatiota ja täydellisyyttä koskevat tulokset, jotka on saatu laajentamalla tai rajoittamalla sen syntaksia ja sen semantiikkaa, ovat laajan kirjallisuuden aihe. Voimme vain sanoa niin paljon ja käsittelemme vain muutamia näistä vaihtoehdoista jättäen muuten tärkeän työn suuret palat dynaamisessa logiikassa.

4.1 PDL ilman testejä

Aksioomikaavio [A?] B ↔ (A → B) näyttää osoittavan, että jokaiselle kaavalle C on olemassa vastaava testivapaa kaava C '-ie, on testivapaa kaava C' sellainen, että ⊨ C ↔ C '. On mielenkiintoista huomata, että tämä väite on virheellinen. Olkoon PDL 0 rajoitus PDL: lle testitöntä säännöllistä ohjelmaa varten, ts. Ohjelmille, jotka eivät sisällä testejä. Berman ja Paterson [1981] katsoivat PDL-kaavan <(p?; Π) *; ¬ p?; Π; p?> 1, mikä on

< kun p do π> p

ja osoitti, että sitä vastaavaa PDL 0- kaavaa ei ole. Siksi PDL: llä on ilmaisuvoimaa enemmän kuin PDL 0: lla. Heidän väitteensä voidaan tosiasiallisesti yleistää seuraavasti. Kaikille n ≥ 0 olkoon PDL n +1 PDL: n osajoukko, jossa ohjelmat voivat sisältää testit A? vain, jos A on PDL n kaava. Kaikille n ≥ 0 Berman ja Paterson pitivät PDL n +1- kaavaa A n +1, jonka määritteli

< kun A n ei π n > <π n > A n

missä A 0  = p ja π 0  = π ja osoittivat, että kaikille n ≥ 0 ei ole PDL n- kaavaa, joka vastaa A n +1. Siksi kaikilla n ≥ 0, PDL n +1: llä on ilmaisuvoimaa enemmän kuin PDL n.

4.2 PDL käänteisellä

CPDL on PDL: n jatke käänteisellä. Se on rakenne, jota on pidetty PDL: n alusta lähtien. Anna kaikkien α-ohjelmien α -1 seisoa uudella semantiikkaohjelmalla

x R (a- 1) y jos y R (a) x.

Käänteinen rakenne antaa meille mahdollisuuden ilmaista tosiasioita nykyistä tilaa edeltävistä valtioista ja perustella ohjelmia taaksepäin. Esimerkiksi [α -1] A tarkoittaa, että ennen a: n suorittamista A: n piti pitää paikassa. Meillä on

⊨ A → [α] <α -1 > A, ⊨ A → [α -1] A.

Käänteisen konstruktion lisääminen ei muuta PDL: n ominaisuuksia merkittävästi. Lisäämällä jokainen seuraavien aksioomikaavioiden esiintymä:

(A8) A → [α] <α -1 >

(A9) A → [α -1]

PDL-todistusjärjestelmään saamme vakaan ja täydellisen vähennyskelpoisuuden predikaatin laajennetulla kielellä. Katso lisätietoja Parikhista [1978]. CPDL: llä on pieni malliominaisuus ja (CPDL-SAT) on EXPTIME-valmis.

On helppo huomata, että CPDL: llä on enemmän ilmaisuvoimaa kuin PDL: llä. Nähdäksesi tämän, ota huomioon CPDL-kaava <π -1 > 1 ja LTS: t M = (W, R, V) ja M '= (W', R ', V'), missä W = {x, y}, R (π) = {(x, y)}, W '= {y'}, R '(π) = ∅ ja V (x) = V (y) = V' (y ') = ∅. Koska M, y sat <π -1 > 1, ei M ', y' sat <π -1 > 1, ja koska kaikille PDL-kaavoille A on tilanne, että M, y sat Affff M ', y' sat A, niin on selvää, että mikään PDL-kaava ei vastaa <π -1 > 1.

4.3 PDL toistuvilla ja silmukoilla

Olemme jo paljastaneet toistovoiman kappaleessa 3.3 ottamalla käyttöön RPDL: n. Täällä tehdään yhteenveto lisää tuloksia RPDL: stä ja sen yhteydestä muihin ohjelmien toistamisen käsitteen muunnelmiin.

RPDL: n monimutkaisusteorian suhteen Streett [1982] oli jo todennut, että RPDL: llä oli äärellinen malliominaisuus; tarkalleen, että jokainen RPDL: n tyydyttävä kaava A on tyydyttävissä mallilla, jonka koko on korkeintaan kolminkertaisesti eksponentiaalinen A: n pituudessa. Automaattiteoreettinen argumentti sallii päätellä, että ongelma (RPDL-SAT) voidaan ratkaista deterministisellä kolminkertaisella eksponentiaalisella ajanjaksolla (3-EXPTIME). Rako tämän päätöksenteon ylärajan (RPDL-SAT) ja yksinkertaisen eksponentiaalisen ajan alarajan (PDL-SAT) välillä oli siten auki. Ongelma osoittautui suuresti yhteydessä tietokonetieteilijöiden kasvavaan kiinnostukseen ajallisen logiikan monimutkaisuuden määrittämisessä, ja erityisesti Kozenin (1983) aiheuttamasta (ehdotuksellisesta) modaalisesta μ-laskennasta (MMC) johtuen, koska RPDL: llä on lineaarinen isku - ylös käännös MMC: lle. Lisäksi,Streettin väite loi jonkin verran ennakkotapausta nykyaikaiselle automaattitekniikoiden käytölle todistamalla ohjelmien logiikan ja ajallisen logiikan laskennalliset ominaisuudet. Julkaisussa Vardi ja Stockmeyer [1985] esitettiin yläraja ei-deterministisessä eksponentiaalisessa ajassa. Emersonissa ja Jutlassa [1988] ja viimeisessä muodossaan Emersonissa ja Jutlassa [1999] osoitettiin, että (MMC-SAT) ja (RPDL-SAT) ovat EXPTIME-täydellisiä. Jos lisäämme kohdan 4.2 kääntöoperaattorin, saadaan CRPDL. (CRPDL-SAT) -järjestelmän monimutkaisuus pysyi avoimena muutaman vuoden, mutta myös sen voidaan osoittaa olevan EXPTIME-täydellinen. Tämä saavutetaan yhdistämällä Emersonin ja Jutlan [1988] ja Vardin [1985] tekniikat, kuten Vardin [1998]. Julkaisussa Vardi ja Stockmeyer [1985] esitettiin yläraja ei-deterministisessä eksponentiaalisessa ajassa. Emersonissa ja Jutlassa [1988] ja viimeisessä muodossaan Emersonissa ja Jutlassa [1999] osoitettiin, että (MMC-SAT) ja (RPDL-SAT) ovat EXPTIME-täydellisiä. Jos lisäämme kohdan 4.2 kääntöoperaattorin, saadaan CRPDL. (CRPDL-SAT) -järjestelmän monimutkaisuus pysyi avoimena muutaman vuoden, mutta myös sen voidaan osoittaa olevan EXPTIME-täydellinen. Tämä saavutetaan yhdistämällä Emersonin ja Jutlan [1988] ja Vardin [1985] tekniikat, kuten Vardin [1998]. Julkaisussa Vardi ja Stockmeyer [1985] esitettiin yläraja ei-deterministisessä eksponentiaalisessa ajassa. Emersonissa ja Jutlassa [1988] ja viimeisessä muodossaan Emersonissa ja Jutlassa [1999] osoitettiin, että (MMC-SAT) ja (RPDL-SAT) ovat EXPTIME-täydellisiä. Jos lisäämme kohdan 4.2 kääntöoperaattorin, saadaan CRPDL. (CRPDL-SAT) -järjestelmän monimutkaisuus pysyi avoimena muutaman vuoden, mutta myös sen voidaan osoittaa olevan EXPTIME-täydellinen. Tämä saavutetaan yhdistämällä Emersonin ja Jutlan [1988] ja Vardin [1985] tekniikat, kuten Vardin [1998].(CRPDL-SAT) -järjestelmän monimutkaisuus pysyi avoimena muutaman vuoden, mutta myös sen voidaan osoittaa olevan EXPTIME-täydellinen. Tämä saavutetaan yhdistämällä Emersonin ja Jutlan [1988] ja Vardin [1985] tekniikat, kuten Vardin [1998].(CRPDL-SAT) -järjestelmän monimutkaisuus pysyi avoimena muutaman vuoden, mutta myös sen voidaan osoittaa olevan EXPTIME-täydellinen. Tämä saavutetaan yhdistämällä Emersonin ja Jutlan [1988] ja Vardin [1985] tekniikat, kuten Vardin [1998].

Kohdassa 3.3 olemme määritellyt predikaatin ∞, missä ∞ (α) tarkoittaa, että α: lla voi olla loputon laskenta. Kutsumme LPDL: ksi logiikkaa, joka saadaan lisäämällä PDL predikaatin ∞ avulla. On selvää, että RPDL on ainakin yhtä ilmeikäs kuin LPDL; ∞ (α): n induktiivinen määritelmä RPDL: n kielellä on sen todistaja. RPDL on itse asiassa ehdottomasti ilmeisempi kuin LPDL. Tämä osoitettiin julkaisuissa Harel ja Sherman [1982]. Kuten voidaan epäillä, sekä RPDL: llä että LPDL: llä on ilmaisuvoimaa enemmän kuin PDL: llä. Se todetaan todistamalla, että joillakin RPDL: n ja LPDL: n kaavoilla ei ole vastaavaa ilmaisua PDL: ssä. Todiste sisältää suodatustekniikan, joka on suunniteltu romahtamaan LTS äärelliseksi malliksi jättäen kuitenkin muuttumattomana totuuden tai tiettyjen kaavojen virheellisyyden. Joillekin PDL-kaavajoukkoille Xse koostuu ryhmittelystä vastaavuusluokkiin LTS: n tiloja, jotka täyttävät täsmälleen samat kaavat kohdassa X. Näin saatu tilojen ekvivalenssiluokkien joukosta tulee suodumallin tilajoukkoja, ja niiden yli rakennetaan siirtymä.

Huolellisesti valitulla joukolla FL (A), joka riippuu PDL-kaavasta A (ns. Fischer-Ladnerin sulkeminen A-alakaavojen joukosta), LTS: n M suodattaminen tuottaa äärellisen suodoksen M ', kuten että A on tyydyttävissä maailmassa u M: ssä ja vain jos se on tyydyttävissä vastaavuusluokassa, joka sisältää u suodoksessa. (Katso Fischer ja Ladner [1979].)

Voimme nyt harkita LTS: n M ((W, R, V)) suodatuksia missä

  • W = {(i, j): j ja i positiiviset kokonaisluvut, 0 ≤ j ≤ i} ∪ {u}
  • (i, j) R (π) (i, j-1), kun 1 ≤ j ≤ i
  • u R (π) (i, i) jokaiselle i: lle
  • V (p) = ∅ jokaiselle p ∈ Φ 0

Yhdessä lauseessa M: ssä tapahtuu, että maailmasta u on ääretön määrä kasvavia pituisia äärellisiä π-polkuja. Meillä on molemmat M, u sat ¬Δπ ja M, u sat ¬ (π *). Silti jokaisella PDL-kaavalla A on sekä Δπ että ∞ (π *), jotka ovat tyytyväisiä u: n ekvivalenssiluokkaan mallissa, joka on saatu suodattamalla M: llä FL (A). Suodatuksen täytyy todellakin romahtaa jotkut M: n tilat ja luoda joitain silmukoita. Siksi ei ole olemassa PDL-kaavaa, joka voisi ilmaista joko Δπ tai ∞ (π *). ja silti meillä on sekä Δπ että ∞ (π *), jotka ovat tyytyväisiä u: n ekvivalenssiluokassa millä tahansa M: n äärellisellä suodoksella. Siten, Δπ tai ∞ (π *) ei voida ilmaista PDL: nä.

On myös muita tapoja tehdä mahdolliseksi väite, jonka ohjelma voi suorittaa ikuisesti. Esimerkiksi, Danecki [1984a] ehdotti predikaatti sloop saada ohjelmia, jotka voivat syöttää vahva silmukoita, joka on:

V (sloop (a)) = {x: x R (a) x}

Kutsutaan SLPDL logiikan, joka on saatu kasvattamalla PDL kanssa sloop (α). RPDL ja SLPDL ovat olennaisesti vertaansa vailla: predikaatti Δ ei ole määritettävissä SLPDL: ssä, ja predikaatti sloop ei ole määritettävissä RPDL: ssä. SLPDL: llä ei ole äärellistä malliominaisuutta. Esimerkiksi kaava

[π *] (1 ∧ ¬ nousu+))

on tyydyttävää vain äärettömissä LTS: issä. Siitä huolimatta Danecki [1984a] vahvisti (SLPDL-SAT) -kaavojen päätettävyyden deterministisellä eksponentiaalisella ajanjaksolla.

4.4 PDL risteyksessä

Toista rakennetta on tutkittu: ohjelmien leikkauskohta. Lisäämällä ohjelmien leikkauspiste PDL: ään, saadaan logiikka IPDL. IPDL: ssä kaikkien ohjelmien α, β lauseke α∩β tarkoittaa uutta ohjelmaa, jolla on semantiikka

xR (aβ) y x x R (a) y ja x R (β) y

Esimerkiksi A: n aiottu luku on, että jos suoritamme α ja β nykyisessä tilassa, niin on olemassa tila, johon molemmat ohjelmat pääsevät saavuttamaan A: n. Tämän seurauksena meillä on

⊨ A → A ∧ A

mutta yleensä meillä on

ei ⊨ A ∧ A → A

Vaikka ohjelmien leikkauksella on tärkeä rooli PDL: n erilaisissa sovelluksissa tekoälyyn ja tietotekniikkaan, PDL: n todisteteoriaa ja kompleksisuuden teoriaa leikkauksen kanssa ei tutkittu useita vuosia. IPDL: n monimutkaisusteorian suhteen vaikeuksia ilmenee, kun tarkastellaan äärellisen mallin ominaisuutta. Itse asiassa konstrukti sloop (α) voidaan ilmaista IPDL. Esittämässä dynaamisessa logiikassa leikkauksen kanssa se on yhtä suuri kuin 1. Voimme siis mukauttaa jakson 4.3 IPDL-kaavaa, ja meillä on

[π *] (1 ∧ [π + ∩1?] 0)

on tyydyttävää vain äärettömissä LTS: issä. Toisin sanoen IPDL: llä ei ole äärellisen mallin ominaisuutta. Danecki [1984b] tutki IPDL: n monimutkaisusteoriaa ja osoitti, että päätöksenteko (IPDL-SAT) voidaan tehdä deterministisessä kaksinkertaisessa eksponentiaalisessa ajassa. (Nykyaikainen todiste esitetään julkaisuissa Göller, Lohrey ja Lutz [2007].) Tämän kaksinkertaisen eksponentiaalisen ajan ylärajan (IPDL-SAT) ja yksinkertaisen eksponentiaalisen ajan alarajan (PDL-SAT) välillä on monimutkaisuusero. hankittu Fischer ja Ladner [1979] pysyi avoinna yli kaksikymmentä vuotta. Vuonna 2004 Lange [2005] perusti eksponentiaalisen avaruuden alarajan (IPDL-SAT). Vuonna 2006Lange ja Lutz [2005] antoivat todistuksen IPDL: n tyydyttämisongelman kaksinkertaisesta eksponentiaaliaika-alarajasta ilman testejä vähentämällä sanan ongelmasta eksponentiaalisesti avaruusrajoitettujen vuorottelevien Turing-koneiden sanamuotoa. Tässä pelkistyksessä iteraatiorakenteen rooli on välttämätön, koska Massacci [2001] mukaan iteraation sisältämättömän IPDL: n tyydyttämisongelma ilman testejä on vain PSPACE-täydellinen. Lisäämällä käänteinen konstrukti IPDL: ään saadaan ICPDL. Göller, Lohrey ja Lutz ovat osoittaneet ICPDL: n tyydyttämisongelman olevan 2-EXPTIME-täydellinen. Göller, Lohrey ja Lutz ovat osoittaneet ICPDL: n tyydyttämisongelman olevan 2-EXPTIME-täydellinen. Göller, Lohrey ja Lutz ovat osoittaneet ICPDL: n tyydyttämisongelman olevan 2-EXPTIME-täydellinen.

IPDL: n todisteteoriassa ilmenee vaikeuksia, kun ymmärrämme, että mikään aksioomikaavio PDL: n kielellä, jossa on leikkaus, "ei vastaa" semantiikkaa x R (α β) y iff x R (α) y ja x R (β) y ohjelman α∩β. Eli ei, esimerkiksi samalla tavalla, että aksioomikaaviot (A1) ja (A2) vastaavasti "vastaavat" ohjelmien α; β ja α∪β semantiikkaa. Tästä syystä PDL: n aksiomatizisaatio risteyksessä oli avoinna, kunnes Balbianissa ja Vakarelovissa [2003] kehitettiin täydellinen todistusjärjestelmä.

Toisessa PDL-variantissa, johtuen Pelegistä [1987] ja jota on edelleen tutkinut Goldblatt [1992b], ilmaisu α∩β tulkitaan”do α ja β samanaikaisesti”. Tässä yhteydessä binaarisuhteet R (α) ja R (β) eivät ole enää muodon (x, y) parien joukkoja x, y-maailmojen kanssa, vaan muodon (x, Y) parisarjoja xa maailma ja Y joukko maailmoja. Sen innoittamana oli Parikhin pelilogiikka [1985], PDL: n tulkinta ohjelmina peleiksi. Game Logic tarjoaa ylimääräisen ohjelmarakenteen, joka kaksinkertaistaa ohjelmat, mikä mahdollistaa ohjelmien leikkauksen määrittelemisen ohjelmien välisenä ei-deterministisen valinnan kaksinaisena.

5. Päätelmät

Tämä artikkeli on keskittynyt ehdotukselliseen dynaamiseen logiikkaan ja joihinkin sen merkittäviin variantteihin. Nykyään on olemassa useita kirjoja - Goldblatt [1982], Goldblatt [1992a], Harel [1979] ja Harel, Kozen ja Tiuryn [2000] - ja tutkimuslehdet - Harel [1984], Kozen ja Tiuryn [1990], Parikh. [1983] - käsittelee PDL: ää ja siihen liittyviä muodollisuuksia. PDL: n tutkimuskokonaisuus on ehdottomasti avuksi kehitettäessä monia järjestelmän dynamiikan loogisia teorioita. Nämä teoriat ovat kuitenkin kiistatta tämän artikkelin ulkopuolella. Van Eijck ja Stokhof [2006] on tuoreempi yleiskatsaus aiheisiin, joissa käytetään dynaamista logiikkaa ja jotka käsittelevät erilaisia teemoja, jotka kiinnostavat filosofia: esimerkiksi viestinnän dynamiikka tai luonnollinen kielen semantiikka. Viimeaikaiset kirjat käsittelevät paljon yksityiskohtaisemmin uusimmista aiheista,kuten dynaaminen tiedon logiikka (dynaaminen episteeminen logiikka) Van Ditmarschissa, Van Der Hoekissa ja Kooissa [2007] ja jatkuvien ja hybridijärjestelmien dynaaminen logiikka (differentiaalinen dynaaminen logiikka) Platzerissä [2010]. PDL suunniteltiin ensisijaisesti ohjelmien perusteluiksi. Ohjelmien perusteluissa on monia muita modaalilogiikan sovelluksia. Algoritminen logiikka on lähempänä PDL: ää, koska sen avulla voidaan puhua nimenomaisesti ohjelmista. Lukijaa kutsutaan tutustumaan Mirkowskassa ja Salwickissa [1987] tutkittuun teokseen. Ajallinen logiikka on nyt teoreettisen tietotekniikan päälogiikka, ja sillä on läheinen yhteys ohjelmien logiikkaan. Niiden avulla voidaan ilmaista siirtymäjärjestelmien ajallinen käyttäytyminen kielellä, joka on abstrakti etiketistä (siis ohjelmat). Katso esimerkiksi Schneider [2004] saadaksesi yleiskuvan tämän tutkimusalueen perusteista.

bibliografia

  • Apt, K., 1981, “Kymmenen vuotta Hoaren logiikkaa: Tutkimus - osa I”, Ohjelmointikieliä ja -järjestelmiä koskevat ACM-tapahtumat, 3 (4): 431–483.
  • Balbiani, P. ja D. Vakarelov, 2003, “PDL ohjelmien leikkauspisteellä: täydellinen aksiomaatio”, Journal of Applied Non-Classical Logics, 13: 231 - 276.
  • van Benthem, J., 1998,”Ohjelmarakenteet, jotka ovat turvallisia bisimulaatiolle”, Studia Logica, 60: 311–330.
  • Berman, F. ja M. Paterson, 1981, "Propositiaalinen dynaaminen logiikka on heikompaa ilman testejä", Theoretical Computer Science, 16: 321–328.
  • Burstall, R., 1974, “Ohjelma todistaa käden simulointina pienellä induktiolla”, tietojenkäsittely 74: IFIP-kongressin 74 julkaisut, Amsterdam: North Holland Publishing Company, 308–312.
  • Danecki, R., 1984a,”Propositional dynaaminen logiikka vahvoilla silmukka-predikaateilla”, julkaisuissa M. Chytil ja V. Koubek, Computer Science Mathematical Foundations of Computer Science, Berliini: Springer-Verlag, 573-581.
  • –––, 1984b,”Epädeterministinen ehdollinen dynaaminen logiikka risteyksellä on päätettävissä”, julkaisussa A. Skowron (toim.), Computation Theory, Berliini: Springer-Verlag, 34-53.
  • De Giacomo, G., ja F. Massacci, 2000, “Vähennysten ja mallien tarkistamisen yhdistäminen taulukkoon ja algoritmeihin käänteistä PDL: tä varten”, Information and Computation, 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,”Dynaamisen logiikan spektri”, julkaisuissa D. Gabbay ja J. Woods (toim.), logiikan historian käsikirja, osa 7 - logiikka ja modaliteetit 1900-luku, Amsterdam: Elsevier, 499–600.
  • Emerson, E., ja Jutla, C., 1988,”Puuautomaattien ja ohjelmien logiikan monimutkaisuus (laajennettu tiivistelmä)”, tietotekniikan perusteita käsittelevän 29. vuosittaisen symposiumin yhteydessä, Los Alamitos, CA: IEEE Computer Society, 328–337.
  • –––, 1999, “Puuautomaatioiden ja ohjelmien logiikan monimutkaisuus”, SIAM Journal of Computing, 29: 132–158.
  • Engeler, E., 1967,”Rakenteiden algoritmiset ominaisuudet”, Matemaattisten järjestelmien teoria, 1: 183–195.
  • Fischer, M. ja R. Ladner, 1979,”Säännöllisten ohjelmien propositiaalinen dynaaminen logiikka”, Journal of Computer and System Sciences, 18: 194–211.
  • Floyd, R., 1967,”Ohjelmien merkityksen osoittaminen”, American Mathematical Society Symposia on Applied Mathematics (Volume 19), Providence, RI: American Mathematical Society, 19–31.
  • Gargov, G. ja S. Passy, 1988,”Determinismi ja silmukointi yhdistelmä-PDL: ssä”, Tietojen teoreettinen tiede, Amsterdam: Elsevier, 259–277.
  • Goldblatt, R., 1982, Tietokoneohjelmoinnin logiikan aksiomatisointi, Berliini: Springer-Verlag.
  • –––, 1992a, ajan ja laskennan logiikka, Stanford: Kieli- ja tietojulkaisujen tutkimuskeskus.
  • –––, 1992b,”Rinnakkaistoiminta: Samanaikainen dynaaminen logiikka riippumattomien modaliteettien kanssa”, Studia Logica, 51: 551–578.
  • Göller, S., M. Lohrey ja C. Lutz, 2007,”Risteys- ja käänteinen PDL on 2EXP-valmis”, Ohjelmistotieteen ja laskennallisten rakenteiden perusteet, Berliini: Springer, 198–212.
  • Harel, D., 1979, ensimmäisen kertaluvun dynaaminen logiikka, Berliini: Springer-Verlag.
  • –––, 1983,”Toistuvat domiinot: tekeminen erittäin päättämättömäksi erittäin ymmärrettäväksi”, julkaisussa M. Karpinski (toim.), Laskentateorian perusteet, Berliini: Springer-Verlag, 177–194.
  • –––, 1984,”Dynaaminen logiikka”, julkaisuissa D. Gabbay ja F. Guenthner (toim.), Filosofisen logiikan käsikirja (osa II), 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,”Looping vs. Repeating in Dynamic Logic”, Information and Control, 55: 175–192.
  • Hoare, C., 1969,”Aksiomaattinen perusta tietokoneohjelmoinnille”, Laskentakoneiden yhdistyksen viestintä, 12: 576–580.
  • Kozen, D., 1983,”Tulokset alustavasta μ-laskennasta”, Teoreettinen tietotekniikka, 27: 333–354.
  • Kozen, D. ja R. Parikh, 1981,”Alkuperäinen todiste PDL: n täydellisyydestä”, Theoretical Computer Science, 14: 113–118.
  • Kozen, D. ja J. Tiuryn, 1990,”Ohjelmien logiikka”, julkaisussa J. Van Leeuwen (toimitettu), Tietojenkäsittelyteoreettiset käsikirjat (osa B), Amsterdam: Elsevier, 789–840.
  • Lange, M., 2005,”Matalampi monimutkaisuus, joka on sidottu ehdotukselliseen dynaamiseen logiikkaan leikkauksen kanssa”, julkaisuissa R. Schmidt, I. Pratt-Hartmann, M. Reynolds ja H. Wansing (toim.), Advances in Modal Logic (Volume 5)), Lontoo: King's College Publications, 133–147.
  • Lange, M. ja C. Lutz, 2005, “2-EXPTIME alarajat ehdotukselle dynaamiselle logiikalle leikkauksella”, Journal of Symbolic Logic, 70: 1072–1086.
  • Lutz, C., 2005,”PDL risteyksessä ja käänteessä on päätettävissä”. Julkaisussa L. Ong (toimitettu), Computer Science Logic, Berliini: Springer-Verlag, 413-427.
  • Massacci, F., 2001,”Päätösmenettelyt ilmeisestä kuvauslogiikasta leikkauksen, koostumuksen, roolien keskustelun ja rooli-identiteetin kanssa”, B. Nebel (toim.), 17. kansainvälinen keinotekoisen älykkyyden yhteiskonferenssi, San Francisco: Morgan Kaufmann, 193-198.
  • Mirkowska, G. ja A. Salwicki, 1987, Algorithmic Logic, Dordrecht: D. Reidel.
  • Nishimura, H., 1979,”Sekvenssimenetelmä dynaamisessa logiikassa”, Acta Informatica, 12: 377–400.
  • Parikh, R., 1978,”Dynaamisen logiikan täydellisyys”, julkaisussa J. Winkowski (toim.), Computer Science Mathematical Foundations of Berlin, Berliini: Springer-Verlag, 1978, 403-415.
  • –––, 1983,”Ohjelmien alustava logiikka: uudet suunnat”, julkaisussa M. Karpinski (toim.), Laskentateorian perusteet, Berliini: Springer-Verlag, 347-359.
  • –––, 1985,”Pelien logiikka ja sen sovellukset”, Annals of Discrete Mathematics, 24: 111–140.
  • Peleg, D., 1987,”samanaikainen dynaaminen logiikka”, Computing Machinery Associationin lehti, 34: 450–479.
  • Platzer, A., 2010, Hybridijärjestelmien looginen analyysi: Lauseiden todistaminen kompleksiselle dynamiikalle, Berliini: Springer, 2010.
  • Pratt, V., 1976,”Semanttiset näkökohdat Floyd-Hoare-logiikasta”, tietotekniikan perusteita käsittelevän IEEE-symposiumin 17. kokouksessa, Los Alamitos, Kalifornia: IEEE Computer Society, 109–121.
  • –––, 1978,”Käytännöllinen päätöksentekomenetelmä ehdotukselle dynaamiselle logiikalle”, ACM: n 10. vuotuisen laskentateorian symposiumin julkaisussa, New York, NY: ACM, 326–337.
  • –––, 1980a,”Lähes optimaalinen menetelmä toiminnan perusteluun”, Journal of Computer and System Sciences, 20: 231–254.
  • –––, 1980b,”Modaalilogiikan soveltaminen ohjelmointiin”, Studia Logica, 39: 257–274.
  • Sakalauskaite, J., ja M. Valiev, 1990,”Dynaamisen logiikan täydellisyys täydellisen toistamisen kanssa”, P. Petkov (toim.), Mathematical Logic, New York: Plenum Press, 339–349.
  • Salwicki, A., 1970,”Muodostuneet algoritmiset kielet”, Bulletin de l'Academie Polonaise des Sciences, Serie des sciences matemaatikot, astronomiset ja fyysiset julkaisut, 18: 227–232.
  • Segerberg, K., 1977,”Täydellisyyslause ohjelmien modaalilogiikassa”, Notices of American Mathematical Society, 24: 522.
  • Schneider, K., 2004, Reaktiivisten järjestelmien todentaminen, Berliini: Springer-Verlag.
  • Streett, R., 1982,”Propositiaalinen dynaaminen silmukoinnin ja keskustelun logiikka on alkeellisesti päätettävissä”, Information and Control, 54: 121–141.
  • Vakarelov, D., 1983,”Suodatuslause dynaamisille algebreille testien ja käänteisen operaattorin kanssa”, julkaisussa A. Salwicki (toim.), Programmes Logics of Programs and niiden Applications, Berliini: Springer-Verlag, 314–324.
  • Vardi, M., 1985,”Vastakkaissuosittelut: Kaksisuuntaisen laskennan perusteet”, tietotekniikan luentomuistiinpanoissa (osa 193), Berliini-Heidelberg: Springer, 413–423.
  • –––, 1998,”Perustelu menneisyydestä kaksisuuntaisilla automaatteilla”, tietotekniikan luentomuistiinpanoissa (osa 1443), Berliini-Heidelberg: Springer, 628–641.
  • Vardi, M., ja Stockmeyer, L., 1985, “Parannettu ylä- ja alaraja ohjelmien modaalilogiikalle: alustava raportti”, ATM: n 17. vuotuisen laskentateorian symposiumin julkaisussa, New York, NY: ACM, 240 -251.
  • Yanov, J., 1959,”Operaattorijärjestelmien vastaavuudesta”, Cybernetic Problems, 1: 1–100.

Akateemiset työkalut

sep mies kuvake
sep mies kuvake
Kuinka mainita tämä merkintä.
sep mies kuvake
sep mies kuvake
Esikatsele tämän tekstin PDF-versio SEP-Ystävien ystävissä.
inpho-kuvake
inpho-kuvake
Katso tätä kirjoitusaihetta Internet Philosophy Ontology Projektista (InPhO).
phil paperit -kuvake
phil paperit -kuvake
Parannettu bibliografia tälle merkinnälle PhilPapersissa, linkkien avulla tietokantaan.

Muut Internet-resurssit

[Ota yhteyttä kirjoittajaan ehdotuksilla.]