@inproceedings{dellanna2022complexity,
      title={The Complexity of Norm Synthesis and Revision}, 
      author={Davide Dell'Anna and Natasha Alechina and Fabiano Dalpiaz and Mehdi Dastani and Maarten Löffler and Brian Logan},
      booktitle = {Proceedings of the 15th International Workshop on Coordination, Organizations, Institutions, Norms, and Ethics for Governance
               of Multi-Agent Systems, {COINE@AAMAS} 2022},
      year={2022},
      url_Link = {https://doi.org/10.1007/978-3-031-20845-4_3},
      url_Paper      = {2022_COINE/COINE22_DellAnnaADDLL.pdf},
      url_Video = {https://www.youtube.com/watch?v=bU6tHw1KORc&t=9041s},
      keywords  = {Data Driven Supervision Of Autonomous Systems, Norms, Multi-Agent Systems, Revision, Synthesis, Complexity, NP Complete},
  abstract = {Norms have been widely proposed as a way of coordinating and controlling the activities of agents in a multi-agent system (MAS). A norm specifies the behaviour an agent should follow in order to achieve the objective of the MAS. However, designing norms to achieve a particular system objective can be difficult, particularly when there is no direct link between the language in which the system objective is stated and the language in which the norms can be expressed. In this paper, we consider the problem of synthesising a norm from traces of agent behaviour, where each trace is labelled with whether the behaviour satisfies the system objective. We show that the norm synthesis problem and several related problems are NP-complete.}
}

{"_id":"KvmKkQrv2ePq7GCom","bibbaseid":"dellanna-alechina-dalpiaz-dastani-lffler-logan-thecomplexityofnormsynthesisandrevision-2022","author_short":["Dell'Anna, D.","Alechina, N.","Dalpiaz, F.","Dastani, M.","Löffler, M.","Logan, B."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","title":"The Complexity of Norm Synthesis and Revision","author":[{"firstnames":["Davide"],"propositions":[],"lastnames":["Dell'Anna"],"suffixes":[]},{"firstnames":["Natasha"],"propositions":[],"lastnames":["Alechina"],"suffixes":[]},{"firstnames":["Fabiano"],"propositions":[],"lastnames":["Dalpiaz"],"suffixes":[]},{"firstnames":["Mehdi"],"propositions":[],"lastnames":["Dastani"],"suffixes":[]},{"firstnames":["Maarten"],"propositions":[],"lastnames":["Löffler"],"suffixes":[]},{"firstnames":["Brian"],"propositions":[],"lastnames":["Logan"],"suffixes":[]}],"booktitle":"Proceedings of the 15th International Workshop on Coordination, Organizations, Institutions, Norms, and Ethics for Governance of Multi-Agent Systems, COINE@AAMAS 2022","year":"2022","url_link":"https://doi.org/10.1007/978-3-031-20845-4_3","url_paper":"2022_COINE/COINE22_DellAnnaADDLL.pdf","url_video":"https://www.youtube.com/watch?v=bU6tHw1KORc&t=9041s","keywords":"Data Driven Supervision Of Autonomous Systems, Norms, Multi-Agent Systems, Revision, Synthesis, Complexity, NP Complete","abstract":"Norms have been widely proposed as a way of coordinating and controlling the activities of agents in a multi-agent system (MAS). A norm specifies the behaviour an agent should follow in order to achieve the objective of the MAS. However, designing norms to achieve a particular system objective can be difficult, particularly when there is no direct link between the language in which the system objective is stated and the language in which the norms can be expressed. In this paper, we consider the problem of synthesising a norm from traces of agent behaviour, where each trace is labelled with whether the behaviour satisfies the system objective. We show that the norm synthesis problem and several related problems are NP-complete.","bibtex":"@inproceedings{dellanna2022complexity,\n title={The Complexity of Norm Synthesis and Revision}, \n author={Davide Dell'Anna and Natasha Alechina and Fabiano Dalpiaz and Mehdi Dastani and Maarten Löffler and Brian Logan},\n booktitle = {Proceedings of the 15th International Workshop on Coordination, Organizations, Institutions, Norms, and Ethics for Governance\n of Multi-Agent Systems, {COINE@AAMAS} 2022},\n year={2022},\n url_Link = {https://doi.org/10.1007/978-3-031-20845-4_3},\n url_Paper = {2022_COINE/COINE22_DellAnnaADDLL.pdf},\n url_Video = {https://www.youtube.com/watch?v=bU6tHw1KORc&t=9041s},\n keywords = {Data Driven Supervision Of Autonomous Systems, Norms, Multi-Agent Systems, Revision, Synthesis, Complexity, NP Complete},\n abstract = {Norms have been widely proposed as a way of coordinating and controlling the activities of agents in a multi-agent system (MAS). A norm specifies the behaviour an agent should follow in order to achieve the objective of the MAS. However, designing norms to achieve a particular system objective can be difficult, particularly when there is no direct link between the language in which the system objective is stated and the language in which the norms can be expressed. In this paper, we consider the problem of synthesising a norm from traces of agent behaviour, where each trace is labelled with whether the behaviour satisfies the system objective. We show that the norm synthesis problem and several related problems are NP-complete.}\n}\n\n","author_short":["Dell'Anna, D.","Alechina, N.","Dalpiaz, F.","Dastani, M.","Löffler, M.","Logan, B."],"key":"dellanna2022complexity","id":"dellanna2022complexity","bibbaseid":"dellanna-alechina-dalpiaz-dastani-lffler-logan-thecomplexityofnormsynthesisandrevision-2022","role":"author","urls":{" link":"https://doi.org/10.1007/978-3-031-20845-4_3"," paper":"http://davidedellanna.com/publications/2022_COINE/COINE22_DellAnnaADDLL.pdf"," video":"https://www.youtube.com/watch?v=bU6tHw1KORc&t=9041s"},"keyword":["Data Driven Supervision Of Autonomous Systems","Norms","Multi-Agent Systems","Revision","Synthesis","Complexity","NP Complete"],"metadata":{"authorlinks":{}},"html":""},"bibtype":"inproceedings","biburl":"http://davidedellanna.com/publications/dellanna.bib","dataSources":["6mqXRucaPuwqWyQEd","Rymgh7KJx3EhNfvG8","2pnuieZznE6L96taK"],"keywords":["data driven supervision of autonomous systems","norms","multi-agent systems","revision","synthesis","complexity","np complete"],"search_terms":["complexity","norm","synthesis","revision","dell'anna","alechina","dalpiaz","dastani","löffler","logan"],"title":"The Complexity of Norm Synthesis and Revision","year":2022}