Abstract
Norms are an important aspect of organizational multiagent systems. However, most important works on norms in MAS do not take the complexity of satisfaction and coherence algorithms into account. In this paper, we propose a language for modelling norms, NODL1, which is based on a fragment of deontic logic and which allows for an efcient computation of norm coherence. This model is based on the Agent/Group/Role (AGR) model, where norms are associated to groups and roles. We show that expressions of this language may be reduced to propositional logic expressions. We then show that evaluating the global coherence of a set of norms is linear in complexity if we do restrain our language to extended Horn clauses.