Logika Hennessy – Milner - Hennessy–Milner logic

v počítačová věda, Logika Hennessy – Milner (HML) je a dynamická logika slouží k určení vlastností a označený přechodový systém (LTS), struktura podobná automat. To bylo představeno v roce 1980 Matthew Hennessy a Robin Milner ve svém příspěvku „O pozorování nedeterminismu a souběžnosti“^[1] (ICALP ).

Další varianta HML zahrnuje použití rekurze k rozšíření expresivity logiky a běžně se označuje jako „Hennessy-Milnerova logika s rekurzí“.^[2] Rekurze je povolena s použitím maximálních a minimálních pevných bodů.

Syntax

Vzorec je definován následujícím způsobem BNF gramatika pro Akt některé sady akcí:

{ displaystyle Phi :: = { textit {tt}} , , , | , , , { textit {ff}} , , , | , , , Phi _ {1} land Phi _ {2} , , , | , , , Phi _ {1} lor Phi _ {2} , , , | , , , [Act] Phi , , , | , , , langle Act rangle Phi}

To znamená, že vzorec může být

neustálá pravda ${ displaystyle { textit {tt}}}$: vždy pravda
konstantní nepravda ${ displaystyle { textit {ff}}}$: vždy nepravdivé
vzorec spojení
vzorec disjunkce
${ displaystyle scriptstyle {[zákon] Phi}}$ vzorec: pro všechny Akt- deriváty, Φ musí držet
${ displaystyle scriptstyle { langle Act rangle Phi}}$ vzorec: pro některé Akt-derivát, Φ musí držet

Formální sémantika

Nechat ${ displaystyle L = (S, { mathsf {Act}}, rightarrow)}$ být označený přechodový systém a nechte ${ displaystyle { mathsf {HML}}}$ být soubor HML vzorců. Vztah uspokojivosti ${ displaystyle {} modely {} subseteq (S times { mathsf {HML}})}$ vztahuje stavy LTS k vzorcům, které splňují, a je definován jako nejmenší relace taková, že pro všechny stavy ${ displaystyle s v S}$ a vzorce ${ displaystyle phi, phi _ {1}, phi _ {2} v { mathsf {HML}}}$ ,

${ displaystyle s modely { textit {tt}}}$ ,
není tam žádný stát ${ displaystyle s v S}$ pro který ${ displaystyle s modely { textit {ff}}}$ ,
pokud existuje stát ${ displaystyle s ' v S}$ takhle ${ displaystyle s { xrightarrow {a}}$ a ${ displaystyle s ' modely phi}$ , pak ${ displaystyle s modely langle a rangle phi}$ ,
pokud pro všechny ${ displaystyle s ' v S}$ takhle ${ displaystyle s { xrightarrow {a}}$ to platí ${ displaystyle s ' modely phi}$ , pak ${ displaystyle s modely [a] phi}$ ,
-li ${ displaystyle s modely phi _ {1}}$ , pak ${ displaystyle s modely phi _ {1} lor phi _ {2}}$ ,
-li ${ displaystyle s modely phi _ {2}}$ , pak ${ displaystyle s modely phi _ {1} lor phi _ {2}}$ ,
-li ${ displaystyle s modely phi _ {1}}$ a ${ displaystyle s modely phi _ {2}}$ , pak ${ displaystyle s modely phi _ {1} land phi _ {2}}$ .

Viz také

The modální μ-kalkul, který rozšiřuje HML o operátoři pevných bodů
Dynamická logika, multimodální logika s nekonečně mnoha způsoby

Reference

^ Hennessy, Matthew; Milner, Robin (1980-07-14). Na pozorování nedeterminismu a souběžnosti. Automaty, jazyky a programování. Přednášky z informatiky. Springer, Berlín, Heidelberg. 299–309. doi:10.1007/3-540-10003-2_79. ISBN 978-3540100034.
^ Holmström, Sören (1990). „Logika Hennessy-Milner s rekurzí jako specifikačním jazykem a na něm založeným výpočtem upřesnění“. Sborník seminářů BCS-FACS o specifikaci a ověřování souběžných systémů: 294–330.

Zdroje

Colin P. Stirling (2001). Modální a časové vlastnosti procesů. Springer. str.32 –39. ISBN 978-0-387-98717-0.
Sören Holmström. 1988. „Hennessy-Milner Logic with Recursion as a Specification Language, and the Refinement Calculus based on it.“. v Sborník seminářů BCS-FACS o specifikaci a ověřování souběžných systémůCharles Rattray (vyd.). Springer-Verlag, Londýn, Velká Británie, 294–330.

Tento počítačová věda článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.

[1] Hennessy, Matthew; Milner, Robin (1980-07-14). Na pozorování nedeterminismu a souběžnosti. Automaty, jazyky a programování. Přednášky z informatiky. Springer, Berlín, Heidelberg. 299–309. doi:10.1007/3-540-10003-2_79. ISBN 978-3540100034.

[HMLwithRecursion-2] Holmström, Sören (1990). „Logika Hennessy-Milner s rekurzí jako specifikačním jazykem a na něm založeným výpočtem upřesnění“. Sborník seminářů BCS-FACS o specifikaci a ověřování souběžných systémů: 294–330.

[1]

[2]