Combinatorial game theory in the form of two-player games has played an important historical role in formal argumentation, logic programming, nonmonotonic reasoning, database query languages, and more recently in data provenance. While such game-based approaches played an integral role early on in formal argumentation, in the study of expressiveness of query languages, and in the quest to ifnd well-behaved semantics for logic programs with recursion through negation, these areas seem to have largely separated from their historical connections, following their own, separate paths with distinct concepts, terminologies, and research results. We touch upon this history and highlight how the use of a single, unstratified logic rule continues to underly many of the approaches developed today within these diferent communities. We argue that a fruitful line of research exists by reconnecting the communities, in a kind of “family reunion”, where results from one community may be transferable to the other (mutatis mutandis), leading to new insights in the neighboring fields. We describe some initial correspondences and connections and invite the community to join our exploration of additional ones.
defeated( ) ← accepted( ) ← ¬ attacks(, ), accepted( ).
defeated( ).
(AF2)
The first rule states that an argument is defeated in an argumentation framework if there
exists an argument that attacks and is accepted. The second rule states that an argument is
accepted if it is not defeated. Dung’s work spawned a large body of research, including families
of models, semantics, tools, and applications of abstract and structured argumentation [
Note that the body of the second rule in AF2 can be placed directly inside the first rule, resulting in a single-rule APU that can be used to compute the defeated arguments (and thus, through complementation, also the accepted arguments): attacks(, ), ¬ defeated( ). (AF) Now compare the single-rule program AF with the following single-rule program WM: move(, ), ¬ win( ).
We can view WM as a game processing unit (GPU) that specifies the solutions of a two-player game: A position in the game is winning (short: a win) if there exists a move to a position such that the new position is lost for the opponent.1 In particular, this means that a position is lost, if there are no more outgoing moves left to play.2
Both logic rules can be seen as close relatives, even “identical twins”, because they can be
understood as syntactic variants of each other, i.e., one can obtain one rule from the other via a
straightforward renaming of relation symbols. For a database theoretician this means that both
rules specify the same query (i.e., the same input-output mapping) up to renaming, as long as
the same semantics is applied (e.g., the three-valued well-founded model semantics [
Consider, e.g., the second rule (WM): It has played a key role in the logic programming,
nonmonotonic reasoning, and database communities in their quest to find the “right” semantics
for unstratified rules with recursion through negation. Recall that a stratified logic program
can use both recursion and negation, but only in a “layered” manner, i.e., where the rule-goal
graph of must not contain negative cycles [6]. For unstratified programs such as AF and
WM, two declarative semantics emerged as the most popular in the 1990s: The more expressive
stable-model semantics [7] (used in answer set programming) and the more skeptical well-founded
semantics [
Similarly, the twin rule AF is an APU that solves argumentation frameworks: Its wellfounded model yields the grounded extension (or grounded labeling) [8, 9] where an argument is defeated, accepted, or undecided if defeated() is True, False, and Undefined , respectively.
Although close connections between formal argumentation on the one hand, and logic
programming, database theory, and game-theory on the other have been known for a long
1In draw-free games the complement of winning is losing; otherwise the complement of winning is losing or drawing.
2For example, a checkmate position in chess!
time [
In database theory, the win-move query expressed by WM has also been used to study the expressive power of query languages [11, 12] and to develop a unified provenance model that can explain the presence and absence of query answers [13, 14]. The game-theoretic notions and concepts developed in these and other database and game-theory papers [15, 16] seem to carry over to argumentation theory and may lead to new insights and results in formal argumentation. Conversely, related notions studied in argumentation theory may carry over to database theory and applications thereof.
Contributions and Game Plan. The purpose of this paper is to foster a “family reunion” of sorts with the goal of developing new insights and findings through cross-fertilization, i.e., by transferring concepts, ideas, and results between communities. Our game plan is as follows: • In Section 2 we recall some standard definitions of argumentation frameworks and introduce basics notions from two-player games, i.e., the win-move game defined by WM. • We kick of the family reunion in Section 3 by describing the nature of the correspondence between the two rules AF and WM and their associated semantics: We show how the grounded extension of an argumentation framework AF corresponds to the well-founded model of an associated win-move game, the Defeatist’s Game DG. In that game, the attack edges of AF are reversed and interpreted as defeated_by moves in DG. We illustrate this correspondence with a running example. • We then introduce another “lost sibling” of the family, i.e., a rule ker that can be used to compute the graph kernels of the move-relation. This gives rise to another correspondence, this time between the stable extensions of AF (which coincide with the stable models of AF) and the graph kernels of DG, which one obtains from the stable models of ker. • The correspondence to graph kernels allows us to transfer an important Decomposition Theorem [15] from game-theory to argumentation frameworks. It turns out that the well-founded model of WM yields this decomposition—and thus further insights into an argumentation framework AF—“for free”. • In Section 4 we introduce query evaluation games, which are a means to reduce query evaluation in databases to solving games. We also briefly compare this to related notions in argumentation, e.g., assumption-based argumentation. • Finally, in Section 5 we discuss how game-based notions of data provenance [13] lend themselves to reinterpretation in argumentation frameworks and thus to new insights and applications in AF. In particular the provenance structure of a solved game graph consists of diferent move types, i.e., winning moves, delaying moves, and bad moves. This edge structure seems to be unexplored in argumentation frameworks so far and thus constitutes another example of cross-fertilization between the diferent communities.
This section provides the basic graph-theoretic definitions and results of abstract argumentation
frameworks and win-move games. The definitions are based on those given in [
Argumentation Frameworks. An argumentation framework AF is a finite, directed graph AF = (, ), whose vertices denote atomic arguments and whose edges ⊆ × denote a binary attacks relation. An edge (, ) ∈ states that argument attacks argument . An example AF is shown in Figure 1a, consisting of arguments a, b, c, . . . , and their attack relation attacks(b, a), attacks(c, a), . . . A subset ⊆ of acceptable arguments is called an extension, provided satisfies certain conditions. An extension is said to attack an argument if an argument ∈ attacks . The attackers of are the arguments that attack at least one argument in . An extension is conflict-free if no argument in attacks another argument in . Conversely, an extension defends an argument if it attacks all attackers of . The arguments defended by are those that defends; this is often described via the characteristic function of an argumentation framework.
Dung [
Similar to an extension, a (reinstatement) labeling [17] assigns each argument in an AF one of three labels, in, out, or undec, such that an argument is labeled in if all its attackers are labeled out, an argument is labeled out if it has an attacker that is labeled in, and an argument is labeled undec otherwise. Caminada showed [17] that a labeling without any undec arguments corresponds to a stable extension, and similarly, a labeling that maximizes undec arguments corresponds to the grounded extension. Figure 1b shows the grounded extension of the argumentation framework in Figure 1a using colors for labels (blue for in, orange for out, yellow for undec). Similarly, Figure 1c shows one of two possible stable extensions of Figure 1a using the same coloring scheme. Note that accepted and defeated correspond to labels in and out, respectively.
In [
c b
c d g a d g f f f f b b k l k l m n m n f f b b a d g a d g c c e h e h e h e h l k l m n m n k l k l m n m n a d g a d g c c e h e h (a) An argumentation framework (b) The grounded extension of (a) (c) A stable extension of (a) (d) A win-move game (e) The well-founded model of (d) (f) A stable model of (d)
A play = 0 → 1 → 2 → · · · is a finite or infinite sequence of edges from where for all = 0, 1, 2, . . . , the edge → +1 is a move (, +1) ∈ . A play is complete if it is infinite or if it ends after = | | moves in a sink of the game graph. The player who cannot move loses the play , while the previous player who made the last move wins . A play of infinite length is a draw, which in finite game graphs WM means that must have a cycle. Figure 1d shows an example game graph (similar but diferent to the AF graph in Figure 1a). Assume e is the start position for Player I. In the play 1 = e → d → f, Player I moves to d and Player II moves to f. Since Player I cannot move from f, Player II wins. However, in 2 = e → h, Player II cannot move, so 2 is won for Player I. Thus, from position e, the “best” move is e → h, whereas the other moves are “bad”: e → d loses, while e → m only draws (if Player II sticks to m → n). To determine the true value of a position ∈ , bad moves are not considered. Instead, only plays are considered where both players play optimally (or at least “good enough”) so that the best possible outcome is guaranteed for both.
The solution of a game consists of assigning one of the labels win, lose, or draw to each position in the game graph WM. Specifically, a position ∈ is assigned the label win if Player I has a winning strategy, i.e., can force a win, no matter how Player II moves. Conversely, is labeled lose, if Player II can force a win, no matter how Player I moves. If neither player can force a win, a position is a draw. Figure 1e shows the labeled solution for the game graph of Figure 1d where colors are used for labels (green ∼ win, red ∼ lose, yellow ∼ draw). A game can be solved by evaluating the rule WM from Section 1 under the well-founded semantics. Similar to the AF in Figure 1a, the win-move rule under the stable-model semantics results in two stable models. However, the interpretation of the stable models (e.g., Fig. 1f) is less intuitive or natural for win-move games, and it is the well-founded model of WM that correctly identifies all won, lost, and drawn positions.
Starting point for our “family reunion” is the observation that the argumentation framework meta-interpreter3 given by the single unstratified rule AF and the “game engine” (or GPU) given by WM are syntactic variants of each other and thus specify the same query in the sense of database theory. In particular, this means that for a given logic programming semantics such as the well-founded or stable semantics, the resulting models of AF and WM are isomorphic.
One minor twist in this correspondence is that the two diferent interpretations of a given graph = (, ), i.e., either as an argumentation framework AF or as a win-move game WM have reversed edge directions (cf. Fig. 1): In the argumentation framework in Fig. 1a, e.g., the edge b → a in means that argument b attacks a. Since the argument b has no attackers, it follows that b is accepted (color-labeled blue in Fig. 1b and Fig. 1c). In the corresponding win-move graph, however, there is a reversed edge a → b, i.e., indicating that a player can move from position a to b in the game. Since there are no further moves possible from b, it follows that in the canonical game semantics, b is lost (red in Fig. 1e and Fig. 1f).
We can understand this edge reversal better by rewriting the APU rule AF as follows: defeated() ← attacked_by(, ), ¬ defeated( ). (AF′ ) Here we replaced the “forward attack” relation attacks(, ) (cf. the three AF graphs in the top row of Fig. 1) by a “backward reasoning” relation attacked_by(, ) analogously to the game relation move(, ) in WM (see the three game graphs in the bottom row of Fig. 1).
With this renaming in place, the following correspondences between the well-founded model of AF′ and WM are immediate: Arguments in the AF correspond to positions in the game. The reverse of the attacks relation, attacks− 1(, ) is the relation attacked_by(, ) and corresponds to move(, ), i.e., the moves of the game.
The Defeatist’s Game. Despite the natural correspondence between grounded extensions of argumentation frameworks and solved win-move games in Fig. 1, this isomorphism under the well-founded semantics can appear unintuitive at first: How is it that accepted arguments (e.g., the blue nodes b and c in Fig. 1b) correspond to lost positions (the red nodes b and c in Fig. 1e) in the game, while defeated arguments (e.g., the orange nodes d and e in Fig. 1b) correspond to won positions (the green nodes in Fig. 1e)?
The answer is that the win-move game WM we are playing to solve an argumentation framework is in fact a “defeatist’s game” DG: In this game, when Player I (the defeatist) starts to move from a position (e.g., a in Fig. 1), the claim made for this position is: a is defeated! The opponent, Player II, begs to difer and tries to demonstrate that argument a is accepted. By design, the defeatist’s game DG from a position is won (for Player I) if is defeated in the grounded extension. Similarly it is lost (for Player I) from position , i.e., argument is accepted, if Player II has a winning strategy, i.e., can force a win. Finally, a drawn position in this game means that argument is undecided in the grounded semantics and no player can force a win.
What is gained by viewing an argumentation framework as a game? After all, game-theoretic
treatments have been part of formal argumentation from the very beginning [
A kernel of a directed graph = (, ) is a subset ⊆ that is both independent and dominating [15]. Here, independent means that no edges exists between vertices in , and dominating means that every vertex in ∖ has a follower (successor) in , i.e., an edge into the kernel . If we view as an argumentation framework AF, but with edges representing the reversed attacked_by relation (as in Fig. 1d), then each kernel corresponds to a stable extension of AF. Similarly, if is viewed as a win-move game WM (again Fig. 1d), then is the set of lost nodes in a stable model of WM (e.g., Fig. 1f depicts one such kernel).
The following unstratified rules ker2 state that if there is an edge from to , where is in the kernel ker, then cannot be in the kernel but instead is in the kernel complement kerc: As in the case of Dung’s APU rules, we can “plug in” the body of the second rule into the first, to obtain another syntactic variant of AF and WM as follows:
edge(, ), ¬kerc( ).
It is easy to see that the stable models of this program can be used to compute all kernels of a digraph: For a given stable model, the kernel consists of all vertices that are not in the kernel complement kerc. Note further that ker is a syntactic variant of WM (and thus also of AF): (ker) (WM)
In other words, the winning positions of a stable model of WM (green in Fig. 1) are precisely the nodes not in the graph kernel of the move relation, while the lost positions (red in Fig. 1) are the nodes in the kernel. Summarizing, we have three syntactic variants AF′ , WM, and ker of a single underlying query “q() ← e(, ), ¬q( )” that encapsulates the common core of all three frameworks: Using the well-founded semantics, we can solve win-move games and compute grounded extensions. Via stable models, we can compute the stable extensions of argumentation frameworks and the kernels of digraphs. There are other results from game theory that carry over to argumentation frameworks as well, as shown next. A Decomposition Theorem. In [15], Fraenkel proves various results regarding structural properties of digraphs kernels. This enables another route to transfer results and insights from games and kernel theory to argumentation frameworks. In [15], Fraenkel shows that: (i) Any digraph = (, ) can be partitioned in (||) time into subsets 1, 2, 3 ⊆ such that 1 lies in all of the kernels (= lost in the well-founded model of WM), 2 lies in the complements of all the kernels (= won in the well-founded model), and on 3 the kernels may be non-unique (= drawn in the well-founded model of WM)—e.g., see Fig. 1e; (ii) can be decomposed into two subgraphs: 1 with vertex set 1 ∪ 2, which has a unique kernel (= the won and lost positions of the well-founded model), and 2 with vertex set 3 (the drawn positions), such that any kernel of is the union of the unique kernel of 1 and some kernel of 2 (if it exists);4 and . . . (iii) . . . since 1 is unique, the total number of kernels in (= number of stable extensions of AF) is determined by the number of kernels of 2.
These and other results [15, 19, 16] reinforce the fundamental connections that exist between win-move games and argumentation frameworks, e.g., via well-founded and stable models. These connections may also shed new light on the intricate connections between forms of skeptical and credulous acceptance, and may lead to new, eficient inference algorithms.
In connecting logic programming and AF, Dung [
s(), ¬t(). be two rules consisting of a query q and a single fact s(a). Assume Player I wants to show that q(a) is an answer and so starts the query game by moving from position q(a) to the rule position 1a . Player II then selects a subgoal of 1a , either s(a) or ¬t(a), to refute. Assuming Player II picks s(a) to refute, Player I then selects the rule 2, denoting the fact s(a), ending the game immediately, as there are no additional moves from 2 (facts have an empty rule body). Thus Player II loses and Player I wins. If Player II had instead chosen to refute ¬t(a), Player I could then have moved to position t(a) (forcing Player II to justify t(a)). Since t(a) is not supported by any rules, this play also ends, and again Player I wins. Since Player I can force a win, no matter how Player II moves, q(a) is an answer to the query.
Fig. 3 gives another example of the translation to game form for a propositional logic program, similar to the examples used for translating logic programs to argumentation frameworks in [22, 10]. The program in Fig. 3a consists of four rules labeled 1 through 4. Using the translation in Fig. 2, the game for is shown as a solved game graph in Fig. 3b. Note that under the well-founded semantics, has a single model where and are Undefined , is True, and is False. This model exactly corresponds to the solved game graph in Fig. 3b where is a
II
I: ∃ (a) Translation pattern I⇌ II II ¬
⇝ ∃ “Atom holds because of rule !” ⇝ “Not satisfied because a subgoal is false!” ⇝ ¬ “Not satisfied because a subgoal ¬ is false!” ¬ ⇝ “Not true, subgoal is false! (Prove me wrong)” (b) Claims made with a move winning position, is a losing position, and both and are drawn. The solved game graph (via position labels and move edges) also contains explanations for the truth-values of atoms relative to the rules of a program. For instance, is true (winning) because it is derived from rule 4 (i.e., there is a move from position to position 4), whose only subgoal ¬ holds (i.e., is false) since is not supported by any rules.
Similarities to LP ⇝ AF Translations. One of the commonly used transformations from logic programs to argumentation frameworks [22, 10] shares some similarities with the query-to-game translation above. In these transformations, an argumentation framework for a propositional logic program consists of arguments representing the rules of the program such that an argument attacks an argument if ’s corresponding rule derives an atom that contradicts a premise of . The rules of Fig. 3a would be translated to the following AF attacks graph: 2 3 1 4 In [10], an argument is associated with each rule’s conclusion (e.g., is the conclusion of rule 1), and a procedure is given that relates the conclusions associated with an extension of the argumentation framework under a given semantics to the set of answers of the corresponding logic program under an equivalent semantics (e.g., grounded extensions with well-founded semantics, and stable extensions with stable models). The grounded extension of the AF above, using the approach in [10], yields the well-founded model of . Similar approaches have been developed, e.g., in [22] for assumption-based argumentation frameworks.
Provenance-based annotations can be added to game graphs [13] and then help to explain the value of positions. We show how these annotations can be adopted directly to explain why arguments are accepted or defeated in grounded AF extensions.
The Length of Plays. Consider the solved game from Fig. 1e, which is shown with additional annotations in Fig. 4a (explained below). Games can be solved in stages. Positions b, f, and h are immediately lost (red nodes): No moves are possible from sink nodes. Next we can infer that 1 : 2 : 3 : 4 : ← ¬ ← ¬ ← ¬ ← ¬ , ¬, ¬ 4 1 ¬ 3 ¬ 2 ¬ (a) Example propositional program .
(b) Corresponding solved win-move game of . positions that have an outgoing move to a lost position (for the opponent) are definitely won (green). Based on our initial determination that b, f, and h are lost, it then follows that a, d, and e are won. What is the status of the remaining positions? The status of c is now determined since all outgoing moves from c definitely end in a node that is won for the opponent ( d and e are already green), so c is objectively lost. Solving a game can thus proceed by iterating the following two labeling rules in stages:6 • Position is won (green) if ∃ move → and position is known to be lost (red) • Position is lost (red) if ∀ moves → , position is known to be won (green) With each position we can associate its length [13], i.e., the stage number when its label first became known. Similarly, we can associate a length with each move, indicating at what stage its type (i.e., edge color) became known. In Fig. 4a, edges into (red) sinks are winning moves (colored green) and labeled with length = 1, so a, d, e and those edges to sink nodes all have length = 1. In the next stage, all successors of c are won, so c itself must be lost, and its length is 1 + the maximal length of any of its succcessors. Similarly, for won , length() = 1 + the minimal length of any lost successor, etc. After a fixpoint is reached, all remaining unlabeled nodes correspond to drawn positions (colored yellow). We set length = ∞ for drawn positions, since neither player can force a win, but both can avoid losing by repeating moves indefinitely. The length ℓ of an edge →ℓ indicates how quickly a player can force a win, or how long a player can delay a loss: In Fig. 4a that position a can be won in as few as one move (to position b), whereas all moves from c delay for only two moves. Similarly, while there is a loop between d and g, position g is lost in only two moves. 6This method corresponds to the alternating fixpoint procedure [25] and to Algorithm 6.1 for computing the grounded labeling of an argumentation framework in [9].
f b 1
3 d g
c 2 2 e 1 h ∞ l ∞ ∞ ∞ m n f b
1
Solved Games Explain it All! Solved games have an intriguing property: Node labels (colors) induce diferent edge types, which in turn can be used to explain why a position is won, lost, or drawn, respectively. Fig. 5 shows how edge types are determined from the color-labels of incident vertices. These types, in turn, induce a downstream provenance (explanation) subgraph that provides the justification or explanation for the status of any ∈ .7 The provenance of position in the solved game is the subgraph reachable from via certain regular path queries (RPQs), where an RPQ is a regular expression over the labels of an edge-labeled directed graph . The answer to an RPQ , given a start node , is the set of nodes reachable along simple paths from whose (concatenated) labels match . Assuming edges are labeled with their edgetype colors, the provenance of a won position matches the RPQ .green.(red.green)* , lost positions match .(red.green)* , and drawn positions match .yellow+. The following examples are drawn from Fig. 4a.
• The provenance of e consists of the single path e → h: e wins because h is lost. • The provenance of d consists of paths d → f and d → g: d wins because f and g are lost. • The provenance of g consists of the path g → d → f: g is lost ultimately because of f. Interpreting Paths in AF. The correspondence described in Section 3 allows us to apply edge lengths and typed edges, e.g., by playing the defeatist’s game, directly to grounded AFs. An 7These explanations are similar in spirit to dialog trees as described in [27].
won (W)
drawn (D) won (W) drawn (D) bad bad lost (L) r: delaying bad n/a y: drawing
lost (L) g: winning n/a n/a bad W bad bad drawing
D winning delaying n/a n/a n/a L example of the grounded AF in Fig. 1b is shown with its provenance information in Fig. 4b. Using this approach, the lengths assigned to attack edges in Fig. 4b correspond to stages of the alternating fixpoint computation applied to attacked_by edges. Thus, edge lengths have a similar interpretation in grounded extensions as in win-move graphs in that they represent the stages in which argument labels become known. Another interpretation of attack-edge lengths is as follows. The length ℓ of an attack edge →ℓ states that argument is the ℓ-th argument along an argument attack chain, i.e., a path composed of only alternating orange (accepted to defeated) and blue (defeated to accepted) edges starting from an accepted argument without any attackers and ending at the last possible defeated argument. Similar to lengths in win-move games, the path (on the attack chain) leading into is assumed to be the shortest such path. For instance, in Fig. 4b, argument b is the first argument in the argument attack chain that terminates at argument a, and thus, the attack edge b → a has the value ℓ = 1. A similar situation exists for arguments f and h. Argument d is the second argument along the (shortest) argument attack chain f → d → c → a, and thus, the edge d → c has the value ℓ = 2. Note that argument g lies on a non-simple argument attack chain where d is the second argument (hence, ℓ = 2 for the edge d → g), making g the third argument on the chain (hence, ℓ = 3 for the edge g → d). Similarly, c is the third argument on two separate argument attack chains of the same path length, and so ℓ = 3 for the edge c → a. Thus, the notion of edge lengths, along with argument labels, can help to clarify the role (i.e., a part of the impact) played by each argument in a grounded argumentation framework.
Explaining Acceptance and Defeat. Similarly to win-move games, an argument’s status in the grounded extension in Fig. 4b can be explained by an RPQ-definable subgraph. To obtain the provenance of defeated and accepted arguments, we adjust the RPQ examples by fixing the end vertex (as opposed to the start vertex) of each RPQ. Assuming edges are labeled with their edgetype colors, the provenance of a defeated position matches the RPQ orange.(blue.orange)* ., accepted positions match (orange.blue)* ., and drawn positions match yellow+.. For Fig. 4b: • The provenance of e consists of the single path h → e: e is defeated since h is accepted. • The provenance of d consists of f → d and g → d: d is defeated since f and g are accepted. • The provenance of g consists of f → d → g: g is accepted ultimately because of f. As in Fig. 4a, the edge-types of Fig. 4b filter out non-relevant attacks within the AF to focus specifcally on those arguments that contribute to acceptance or non-acceptance of an argument.
Games have played an important role in the study of database query languages and in finding acceptable arguments in argumentation frameworks. While these approaches share a common history, it appears the communities have largely separated (or possibly haven’t had much overlap to begin with). The goal of this paper was to demonstrate some of the deep underlying connections that exist, exemplified by the win-move rule WM and its twin-rules8 AF and ker, and to use these to reestablish the lost family ties. We believe that a fruitful line of research can be established by reconnecting the communities and transfering concepts, tools, and results between them, leading to further cross-fertilization and new insights.
The results from database theory for the query WM presented here should look familiar to researchers in formal argumentation. Our starting point was the straightforward link between AF and WM: Twin rules that have their distinct histories and applications in separate communities, but that haven’t been studied together, at least to the best of our knowledge. Under the well-founded semantics, the solved win-move game WM—with its additional structure and “built-in” provenance–corresponds to the grounded labeling of an argumentation framework [17, 9]. The additional provenance structure induced by edge types (“not all edges are created equal”) [13] and the decomposition results about graph kernels [15] immediately suggest corresponding structures for argumentation frameworks, both of which appear to be new results in abstract argumentation.
Finally, we invite feedback and welcome collaboration opportunities on these and similar questions. An open source demonstration using Jupyter notebooks, including the example from Fig. 4, is available [28]. We plan to evolve and expand these notebooks as teaching materials for some of our undergraduate and graduate courses, covering knowledge representation and reasoning, information modeling, and database theory.
[6] K. R. Apt, H. A. Blair, A. Walker, Towards a Theory of Declarative Knowledge, in: J. Minker (Ed.), Foundations of Deductive Databases and Logic Programming, 1988, pp. 89–148. [7] M. Gelfond, V. Lifschitz, The Stable Model Semantics for Logic Programming, in: ILPS, 1988, pp. 1070–1080. [8] M. W. A. Caminada, D. M. Gabbay, A Logical Account of Formal Argumentation, Studia
Logica 93 (2009). [9] S. Modgil, M. Caminada, Proof Theories and Algorithms for Abstract Argumentation
Frameworks, in: Argumentation in Artificial Intelligence, 2009, pp. 105–129. [10] M. Caminada, S. Sá, J. Alcântara, W. Dvořák, On the Equivalence between Logic Programming Semantics and Argumentation Semantics, Approx. Reasoning 58 (2015) 87–111. [11] P. G. Kolaitis, The expressive power of stratified logic programs, Information and Computation 90 (1991) 50–66. [12] J. Flum, M. Kubierschky, B. Ludäscher, Total and Partial Well-Founded Datalog Coincide, in: ICDT, LNCS 1186, Springer, 1997, pp. 113–124. [13] S. Köhler, B. Ludäscher, D. Zinn, First-order provenance games, in: In Search of Elegance in the Theory and Practice of Computation, LNCS 8000, 2013, pp. 382–399. [14] S. Lee, S. Köhler, B. Ludäscher, B. Glavic, A SQL-Middleware Unifying Why and Why-Not
Provenance for First-Order Queries, in: ICDE, 2017, pp. 485–496. [15] A. Fraenkel, Combinatorial Game Theory Foundations Applied to Digraph Kernels, Electronic Journal of Combinatorics 4 (1997) 1–17. [16] J. Flum, Games, Kernels, and Antitone Operations, Order 17 (2000) 61–73. [17] M. Caminada, On the Issue of Reinstatement in Argumentation, in: Logics in Artificial
Intelligence, LNAI 4160, Springer, 2006, pp. 111–123. doi:10.1007/11853886_11. [18] J. von Neumann, O. Morgenstern, A. Rubinstein, Theory of Games and Economic Behavior (60th Anniversary Commemorative Edition), Princeton University Press, 1944. [19] B. v. Karger, R. Berghammer, Computing kernels in directed bichromatic graphs, Information Processing Letters 62 (1997) 5–11. doi:10.1016/S0020-0190(97)00035-5. [20] Y. Dimopoulos, A. Torres, Graph theoretical structures in logic programs and default theories, Theoretical Computer Science 170 (1996) 209–244. [21] E. Boros, V. Gurvich, Perfect graphs, kernels, and cores of cooperative games, Discrete
Mathematics 306 (2006) 2336–2354. [22] P. M. Dung, R. A. Kowalski, F. Toni, Dialectic proof procedures for assumption-based, admissible argumentation, AI 170 (2006) 114–159. [23] A. K. Chandra, D. Harel, Horn clause queries and generalizations, The Journal of Logic
Programming 2 (1985) 1–15. doi:10.1016/0743-1066(85)90002-0. [24] S. Abiteboul, R. Hull, V. Vianu, Foundations of Databases, Addison-Wesley, 1995. [25] A. Van Gelder, The alternating fixpoint of logic programs with negation, Journal of
Computer and System Sciences 47 (1993) 185–221. [26] B. Ludäscher, Y. Xia, Games and argumentation: Time for a family reunion!, in: Fourth
Workshop on Explainable Logic-Based Knowledge Representation (XLoKR), 2023. [27] P. M. Dung, P. Mancarella, F. Toni, Computing ideal sceptical argumentation, AI 171 (2007) 642–674. [28] Y. Xia, S. Bowers, B. Ludäscher, Games and argumentation demo repository, 2023. github.com/idaks/Games-and-Argumentation-AI3.