In computer science, Hennessy–Milner logic (HML) is a dynamic logic used to specify properties of a labeled transition system (LTS), a structure similar to an automaton. It was introduced in 1980 by Matthew Hennessy and Robin Milner in their paper "On observing nondeterminism and concurrency" (ICALP).
Another variant of the HML involves the use of recursion to extend the expressibility of the logic, and is commonly referred to as 'Hennessy-Milner Logic with recursion'. Recursion is enabled with the use of maximum and minimum fixed points.
A formula is defined by the following BNF grammar for Act some set of actions:
Φ
::=
tt
|
ff
|
Φ
1
∧
Φ
2
|
Φ
1
∨
Φ
2
|
[
A
c
t
]
Φ
|
⟨
A
c
t
⟩
Φ
That is, a formula can be
constant truth
tt
always true
constant false
ff
always false
formula conjunction
formula disjunction
[
L
]
Φ
formula
for all
Act-derivatives,
Φ must hold
⟨
L
⟩
Φ
formula
for some
Act-derivative,
Φ must hold
Let
L
=
(
S
,
A
c
t
,
→
)
be a labeled transition system, and let
H
M
L
be the set of HML formulae. The satisfiability relation
⊨
⊆
(
S
×
H
M
L
)
relates states of the LTS to the formulae they satisfy, and is defined as the smallest relation such that, for all states
s
∈
S
and formulae
ϕ
,
ϕ
1
,
ϕ
2
∈
H
M
L
,
s
⊨
tt
,
if there exists a state
s
′
∈
S
such that
s
→
a
s
′
and
s
′
⊨
ϕ
, then
s
⊨
⟨
a
⟩
ϕ
,
if for all
s
′
∈
S
such that
s
→
a
s
′
it holds that
s
′
⊨
ϕ
, then
s
⊨
[
a
]
ϕ
,
if
s
⊨
ϕ
1
, then
s
⊨
ϕ
1
∨
ϕ
2
,
if
s
⊨
ϕ
2
, then
s
⊨
ϕ
1
∨
ϕ
2
,
if
s
⊨
ϕ
1
and
s
⊨
ϕ
2
, then
s
⊨
ϕ
1
∧
ϕ
2
.
