{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,12]],"date-time":"2024-07-12T15:58:45Z","timestamp":1720799925906},"reference-count":0,"publisher":"IOS Press","license":[{"start":{"date-parts":[[2022,9,7]],"date-time":"2022-09-07T00:00:00Z","timestamp":1662508800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,9,7]]},"abstract":"<jats:p>Typically in abstract argumentation, one starts with arguments and a defeat relation, and applies some semantics in order to determine the acceptability status of the arguments. We consider the converse case where we have knowledge of the acceptability status of arguments and want to identify a defeat relation that is consistent with the known acceptability data \u2013 the \u03c3-consistency problem. Focusing on complete semantics as underpinning the majority of the major semantic types, we show that the complexity of determining a defeat relation that is consistent with some set of acceptability data is highly dependent on how the data is labelled. The extension-based 2-valued \u03c3-consistency problem for complete semantics is revealed as NP-complete, whereas the labelling-based 3-valued \u03c3-consistency problem is solvable within polynomial time. We then present an informal discussion on application to grounded, stable, and preferred semantics.<\/jats:p>","DOI":"10.3233\/faia220158","type":"book-chapter","created":{"date-parts":[[2022,9,13]],"date-time":"2022-09-13T14:22:13Z","timestamp":1663078933000},"source":"Crossref","is-referenced-by-count":2,"title":["On the Complexity of Determining Defeat Relations Consistent with Abstract Argumentation Semantics"],"prefix":"10.3233","author":[{"given":"Jack","family":"Mumford","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Liverpool, UK"},{"name":"Department of Informatics, King\u2019s College London, UK"}]},{"given":"Isabel","family":"Sassoon","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Brunel University London, UK"}]},{"given":"Elizabeth","family":"Black","sequence":"additional","affiliation":[{"name":"Department of Informatics, King\u2019s College London, UK"}]},{"given":"Simon","family":"Parsons","sequence":"additional","affiliation":[{"name":"School of Computer Science, University of Lincoln, UK"}]}],"member":"7437","container-title":["Frontiers in Artificial Intelligence and Applications","Computational Models of Argument"],"original-title":[],"link":[{"URL":"https:\/\/ebooks.iospress.nl\/pdf\/doi\/10.3233\/FAIA220158","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,13]],"date-time":"2022-09-13T14:22:24Z","timestamp":1663078944000},"score":1,"resource":{"primary":{"URL":"https:\/\/ebooks.iospress.nl\/doi\/10.3233\/FAIA220158"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,7]]},"references-count":0,"URL":"https:\/\/doi.org\/10.3233\/faia220158","relation":{},"ISSN":["0922-6389","1879-8314"],"issn-type":[{"value":"0922-6389","type":"print"},{"value":"1879-8314","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,9,7]]}}}