Norm approximation for imperfect monitors

In this paper, we consider the runtime monitoring of norms with
imperfect monitors. A monitor is imperfect for a norm if it has
insufficient observational capabilities to determine if a given execution
trace of a multi-agent system complies with or violates the
norm. One approach to the problem of imperfect monitors is to enhance
the observational capabilities of the normative organisation.
However this may be costly or in some cases impossible. Instead
we show how to synthesise an approximation of an ‘ideal’ norm
that can be perfectly monitored given a monitor, and which is optimal
in the sense that any other approximation would fail to detect at
least as many violations of the ideal norm. We give a logical analysis
of (im)perfect monitors. We state the computational complexity
of the norm approximation problem, and give an optimal algorithm
for generating optimal approximations of norms given a monitor.