| dc.date.accessioned |
2017-04-11T10:08:11Z |
und |
| dc.date.accessioned |
2017-10-24T12:24:22Z |
|
| dc.date.available |
2017-04-11T10:08:11Z |
und |
| dc.date.available |
2017-10-24T12:24:22Z |
|
| dc.date.issued |
2017-04-11T10:08:11Z |
|
| dc.identifier.uri |
http://radr.hulib.helsinki.fi/handle/10138.1/6000 |
und |
| dc.identifier.uri |
http://hdl.handle.net/10138.1/6000 |
|
| dc.title |
Enforcement in Abstract Argumentation via Boolean Optimization |
en |
| ethesis.discipline |
Computer science |
en |
| ethesis.discipline |
Tietojenkäsittelytiede |
fi |
| ethesis.discipline |
Datavetenskap |
sv |
| ethesis.discipline.URI |
http://data.hulib.helsinki.fi/id/1dcabbeb-f422-4eec-aaff-bb11d7501348 |
|
| ethesis.department.URI |
http://data.hulib.helsinki.fi/id/225405e8-3362-4197-a7fd-6e7b79e52d14 |
|
| ethesis.department |
Institutionen för datavetenskap |
sv |
| ethesis.department |
Department of Computer Science |
en |
| ethesis.department |
Tietojenkäsittelytieteen laitos |
fi |
| ethesis.faculty |
Matematisk-naturvetenskapliga fakulteten |
sv |
| ethesis.faculty |
Matemaattis-luonnontieteellinen tiedekunta |
fi |
| ethesis.faculty |
Faculty of Science |
en |
| ethesis.faculty.URI |
http://data.hulib.helsinki.fi/id/8d59209f-6614-4edd-9744-1ebdaf1d13ca |
|
| ethesis.university.URI |
http://data.hulib.helsinki.fi/id/50ae46d8-7ba9-4821-877c-c994c78b0d97 |
|
| ethesis.university |
Helsingfors universitet |
sv |
| ethesis.university |
University of Helsinki |
en |
| ethesis.university |
Helsingin yliopisto |
fi |
| dct.creator |
Niskanen, Andreas |
|
| dct.issued |
2017 |
|
| dct.language.ISO639-2 |
eng |
|
| dct.abstract |
Computational aspects of argumentation are a central research topic of modern artificial intelligence. A core formal model for argumentation, where the inner structure of arguments is abstracted away, was provided by Dung in the form of abstract argumentation frameworks (AFs). AFs are syntactically directed graphs with the nodes representing arguments and edges representing attacks between them. Given the AF, sets of jointly acceptable arguments or extensions are defined via different semantics. The computational complexity and algorithmic solutions to so-called static problems, such as the enumeration of extensions, is a well-studied topic.
Since argumentation is a dynamic process, understanding the dynamic aspects of AFs is also important. However, computational aspects of dynamic problems have not been studied thoroughly. This work concentrates on different forms of enforcement, which is a core dynamic problem in the area of abstract argumentation. In this case, given an AF, one wants to modify it by adding and removing attacks in a way that a given set of arguments becomes an extension (extension enforcement) or that given arguments are credulously or skeptically accepted (status enforcement).
In this thesis, the enforcement problem is viewed as a constrained optimization task where the change to the attack structure is minimized. The computational complexity of the extension and status enforcement problems is analyzed, showing that they are in the general case NP-hard optimization problems. Motivated by this, algorithms are presented based on the Boolean optimization paradigm of maximum satisfiability (MaxSAT) for the NP-complete variants, and counterexample-guided abstraction refinement (CEGAR) procedures, where an interplay between MaxSAT and Boolean satisfiability (SAT) solvers is utilized, for problems beyond NP. The algorithms are implemented in the open source software system Pakota, which is empirically evaluated on randomly generated enforcement instances. |
en |
| dct.subject |
abstract argumentation |
en |
| dct.subject |
argumentation dynamics |
en |
| dct.subject |
computational complexity |
en |
| dct.subject |
maximum satisfiability |
en |
| dct.language |
en |
|
| ethesis.language.URI |
http://data.hulib.helsinki.fi/id/languages/eng |
|
| ethesis.language |
English |
en |
| ethesis.language |
englanti |
fi |
| ethesis.language |
engelska |
sv |
| ethesis.thesistype |
pro gradu-avhandlingar |
sv |
| ethesis.thesistype |
pro gradu -tutkielmat |
fi |
| ethesis.thesistype |
master's thesis |
en |
| ethesis.thesistype.URI |
http://data.hulib.helsinki.fi/id/thesistypes/mastersthesis |
|
| dct.identifier.urn |
URN:NBN:fi-fe2017112251305 |
|
| dc.type.dcmitype |
Text |
|
