Argumentation Theory o ers formalisms for the study of reasoning processes taking place between intelligent entities. In this context, time is a crucial factor: in a real-world environment, activities have a determined temporal duration and the behaviour of agents is in uenced by the actions previously taken. While agent-based modelling languages naturally implement concurrency and time constraints, the currently available languages for argumentation do not allow to explicitly model this type of behaviours. In this paper, we propose a language for modelling concurrent interaction between agents that also allows the specication of temporal intervals in which particular actions occur. Such a language, that we call Timed Concurrent Language for Argumentation, allows agents to communicate with each other and to reason on the acceptability of their beliefs with respect to a given time interval. We also show how Timed Abstract Argumentation Frameworks can be modelled by combining time and concurrency.
Argumentation Theory pursues the objective of studying how conclusions can be reached, starting from a set of assumptions, through a process of logical reasoning. This process is very similar to the human way of thinking and involves features which can be traced to a form of dialogue between two (or more) people. Abstract Argumentation Frameworks [16], AFs in short, are used to study the acceptability of arguments according to given selection criteria. Formalisms like Timed Abstract Argumentation Frameworks (TAFs) [10,14,15] have been proposed to meet the need for including the notion of time into argumentation processes. Time is a particularly important aspect of cooperative environments: in many \real-life" applications, the activities have a temporal duration (that can be even interrupted) and the coordination of such activities has to take into consideration this timeliness property. The interacting actors are mutually ? Copyright c 2021 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). in uenced by their actions, meaning that agent A reacts accordingly to the timing and quantitative aspects related to the behaviour of agent B, and vice versa. Moreover, the information brought forward by debating agents that interact in a dynamic environment can be a ected by time constraints, limiting, for instance, the in uence of some arguments in the system to a certain time lapse. A mechanism for handling time is therefore required to better model the behaviour of intelligent agents involved in argumentation processes.
With this paper, we introduce the Timed Concurrent language for Argumentation (tcla), a timed extension of cla [5,6], which models dynamic interactions between agents and uses notions from Argumentation Theory to reason about shared knowledge. We provide both the syntax and the operational semantics. Coordinating agents that need to take decisions both on arguments and attacks and time events may bene t from this language. Such agents can be used, for instance, to implement TAFs, namely extended AFs in which arguments are only available for a given temporal interval. The language we present is well suited for this kind of tasks, as Section 4 shows with examples. More complex dynamics could also be considered: for example, an argument could be made available only if speci c conditions are met, and agents could be given priorities in introducing arguments for certain time intervals.
tcla is based on the hypothesis of bounded asynchrony [25]: any computation takes a bounded period of time rather than being instantaneous as in the concurrent synchronous languages esterel [3], lustre [17], signal [20] and Statecharts [18]. Time itself is measured by a discrete global clock, i.e., the internal clock of the tcla process. In tcla, we directly introduce a timed interpretation of the programming constructs by identifying a time-unit with the time needed for the execution of a basic action (that can be an addition, a removal or a check of arguments/attacks, or a semantical test of arguments), and by interpreting action pre xing (!) as the next-time operator. An explicit timing primitive is also introduced in order to allow for the speci cation of timeouts. Note that we consider a paradigm where parallel operations are expressed in term of maximal parallelism. According to the maximal parallelism policy, at each moment, every enabled agent of the system is activated, while in the interleaving paradigm only one of the enabled agents is executed instead. By using maximal parallelism, time passes for all the parallel processes involved in a computation. This approach, analogous to the one adopted in [8,4,25], is di erent from the one of [9], where time elapsing is interpreted in terms of interleaving, although assuming maximal parallelism for actions depending on time. Our proposal is also di erent from the one in [11], where time does not elapse for timeout constructs.
The rest of the paper is organised as follows: in Section 2 we summarise the most important background notions and frameworks from which tcla derives. In Section 3 we present tcla and the operational semantics of its agents. Section 4 exempli es the use of timed paradigms in tcla and shows an application example of how a TAF can be dynamically instantiated, highlighting the relation between tcla and TAFs. Section 5 describes some related work, and Section 6 concludes the paper by also indicating future research lines. 2
Argumentation Theory aims to understand and model the human natural fashion of reasoning, allowing one to deal with uncertainty in non-monotonic (defeasible) reasoning. In his seminal paper [16], Dung de nes the building blocks of abstract argumentation.
De nition 1 (AFs). Let U be the set of all available arguments3, which we refer to as the \universe". An Abstract Argumentation Framework is a pair hArg; Ri where Arg U is a set of adopted arguments and R is a binary relation on Arg.
For two arguments a; b 2 Arg, the notation (a; b) 2 R represents an attack directed from a against b. We de ne the sets of arguments that attack (and that are attacked by) another argument as follows.
De nition 2 (Attacks). Let F = hArg; Ri be an AF, a 2 Arg and S Arg. We de ne the sets aF+ = fb 2 Arg j (a; b) 2 Rg, aF = fb 2 Arg j (b; a) 2 Rg, SF+ = Sa2S aF+ and SF = Sa2S aF (we will omit the subscript F when it is clear from the context).
De nition 3 (Acceptable Argument). Given an AF F = hArg; Ri, an argument a 2 Arg is acceptable with respect to D Arg if and only if 8b 2 Arg such that (b; a) 2 R, 9c 2 D such that (c; b) 2 R, and we say that a is defended from D.
By using the notion of defence as a criterion for distinguishing acceptable sets of arguments (extensions) in the framework, one can further re ne the set of selected \good" arguments. The goal is to establish which are the acceptable arguments according to a certain semantics, namely a selection criterion. Non-accepted arguments are rejected. Di erent kinds of semantics have been introduced [16,1] that re ect qualities which are likely to be desirable. We rst recall de nitions for the extension-based semantics [16], namely admissible, complete, stable, semi-stable, preferred, and grounded semantics (denoted with adm, com, stb, sst, prf and gde, respectively, and generically with ). De nition 4 (Extension-based semantics). Let F = hArg; Ri be an AF. A set E Arg is con ict-free in F , denoted E 2 Scf (F ), when there are no a; b 2 E such that (a; b) 2 R. For E 2 Scf (F ) we have that: { E 2 Sadm(F ) when each a 2 E is defended by E4; 3 The set U is not present in the original de nition by Dung and we introduce it for our convenience. 4 If E 2 Sadm(F ) we say that E is an admissible extension of F . Analogously for the other semantics. { E 2 Scom(F ) when E 2 Sadm(F ) and 8a 2 Arg defended by E, a 2 E; { E 2 Sstb(F ) when 8a 2 Arg n E, 9b 2 E such that (b; a) 2 R; { E 2 Ssst(F ) when E 2 Scom(F ) and E [ E+ is maximal; { E 2 Sprf (F ) when E 2 Sadm(F ) and E is maximal; { E 2 Sgde(F ) when E 2 Scom(F ) and E is minimal.
Besides enumerating the extensions for a certain semantics , one of the most common tasks performed on AFs is to decide whether an argument a is accepted in some extension of S (F ) or in all extensions of S (F ). In the former case, we say that a is credulously accepted with respect to ; in the latter, a is instead sceptically accepted with respect to .
Example 1. In Figure 1 we provide an example of AF where sets of extensions are given for all the mentioned semantics: Scf (F ) = ffg, fag, fbg, fcg, fdg, fa; cg, fa; dg, fb; dgg, Sadm(F ) = ffg, fag, fcg, fdg, fa; cg, fa; dgg, Scom(F ) = ffag, fa; cg, fa; dgg, Sprf (F ) = ffa; cg, fa; dgg, Sstb(F ) = Ssst(F ) = ffa; dgg, and Sgde(F ) = ffagg. To conclude the example, we want to point out that argument a is sceptically accepted with respect to the complete semantics, since it appears in all three subsets of Scom(F ). On the other hand, arguments c, that is in just one complete extension, is credulously accepted with respect to the complete semantics.
Many of the above-mentioned semantics (such as the admissible and the complete ones) exploit the notion of defence in order to decide whether an argument is part of an extension or not. The phenomenon for which an argument is accepted in some extension because it is defended by another argument belonging to that extension is known as reinstatement [12]. In the same paper, Caminada also gives a de nition for a reinstatement labelling.
De nition 5 (Reinstatement labelling). Let F = hArg; Ri be an AF and L = fin; out; undecg. A labelling of F is a total function L : Arg ! L. We de ne in(L) = fa 2 Arg j L(a) = ing, out(L) = fa 2 Arg j L(a) = outg and undec(L) = fa 2 Arg j L(a) = undecg. We say that L is a reinstatement labelling if and only if it satis es the following: { 8a 2 Arg : a 2 in(L) () 8b 2 Arg j (b; a) 2 R : b 2 out(L) { 8a 2 Arg : a 2 out(L) () 9b 2 Arg j (b; a) 2 R ^ b 2 in(L)
In other words, an argument is labelled in if all its attackers are labelled out, and it is labelled out if at least an in node attacks it. In all other cases, the argument is labelled undec. A labelling-based semantics [1] associates with an AF a subset of all the possible labellings. In Figure 2 we show an example of reinstatement labelling on an AF in which arguments a and c highlighted in green are in, red ones (b and d) are out, and the the yellow argument e (that attacks itself) is undec.
Labelling restrictions Semantics no restrictions complete empty undec stable minimal undec semi-stable maximal in preferred maximal out preferred maximal undec grounded minimal in grounded minimal out grounded
Given a labelling L, it is possible to identify a correspondence with the extension-based semantics [1]. In particular, the set of in arguments coincides with a complete extension, while other semantics can be obtained through restrictions on the labelling as shown in Table 1.
The notion of time can be included into the reasoning model of AFs by considering temporal intervals [15] de ned as follows.
De nition 6 (Temporal Interval). A temporal interval is a pair built from t1; t2 2 Z in one of the following ways: { [t1; t1], denoting the moment t1; { [t1; 1), a set of moments formed by all the numbers in Z greater than or equal to t1; { ( 1; t2], a set of moments formed by all the numbers in Z smaller than or equal to t2; { [t1; t2], a set of moments formed by all the numbers in Z from t1 to t2 (both included); { ( 1; 1), denoting a set of moments formed by all the numbers in Z.
In Timed Argumentation Frameworks [14,15], each argument is associated with temporal intervals that express the period of time in which the argument is available.
De nition 7 (TAFs). A timed abstract argumentation framework is a tuple hArg; R; Avi where Arg U is a set of adopted arguments belonging to the universe U , R5 is a binary relation on Arg, and Av : Arg ! }( ) is the availability function for timed arguments.
We illustrate in Figure 3 an example of the behaviour of timed arguments taken from [15], with availability function de ned as Av(a) = f[10; 40]; [60; 75]g, Av(b) = f[30; 50]g, Av(c) = f[20; 40]; [45; 55]; [60; 70]g, Av(d) = f[47; 65]g and Av(e) = f( 1; 44]g. Note that attack relations in a TAF never change, but are only considered when availability of both the attacker and the attacked arguments overlaps (alternatively, we can consider attacks to blink together with the arguments they connect). We can imagine the modi cations at a given instant t taking place simultaneously, as if every argument of the TAF was handled (made available/not available) by a di erent agent.
Given a semantics , the set of acceptable arguments in a TAF can be computed with respect to a certain moment t by only considering arguments (and attacks) available at t. For example, in the TAF of Figure 3, the singleton fbg is an admissible extension for t 2 (41; 44), that is when b itself is available and its attacker c is not. 5 Note that in certain time intervals, attacks could be de ned between arguments not currently available in the TAF.
47 44 time 60
75 65 a b c d e 10
40 30
50 20
tcla Syntax and Semantics The syntax of our Timed Concurrent Language for Argumentation, tcla, is presented in Table 2, where, as usual, P , C, A and E denote a generic process, a sequence of procedure declarations (or clauses), a generic agent and a generic guarded agent, respectively. Moreover t 2 N [ f+1g. In Tables 3 and 4, then, we give the de nitions for the transition rules.
p(a; l; ; i)
E +P E j EkGE P ::= C:A C ::= p(a; l; ; i) :: A j C:C A ::= success j f ailure j add(Arg; R) ! A j rmv(Arg; R) ! A j E j AkA j 9xA j E ::= testc;t(a; l; ) ! A j tests;t(a; l; ) ! A j checkt(Arg; R) ! A j E + E j
Communication between tcla agents is implemented via shared memory, similarly to cla [5] and CC [26], and opposed to other languages (e.g., CSP [19] and CCS [23]) based on message passing. In the following, we denote by E the class of guarded agents and by E0 the class of guarded agents such that all outermost guards have t = 0 (note that a Boolean syntactic category could be introduced in replacement of E0 to better handle guards and allow for ner distinctions). In a tcla process P = C.A, A is the initial agent, to be executed in the context of the set of declarations C.
The operational model of tcla processes can be formally described by a transition system T = (Conf ; !), where we assume that each transition step exactly takes one time-unit. Con gurations (in) Conf are pairs consisting of a process and an AF F = hArg; Ri representing the common knowledge base. The transition relation ! Conf Conf is the least relation satisfying the rules in Tables 3 and 4, and it characterises the (temporal) evolution of the system. So, hA; F i ! hA0; F 0i means that, if at time t we have the process A and the framework F , then at time t + 1 we have the process A0 and the framework F 0.
In Tables 3 and 4 we have omitted the symmetric rules for the choice operator + and for the two parallel composition operators k and kG. Indeed, + is commutative, so E1 + E2 produces the same result as (that is, is congruent to) E2 + E1. The same is also true for k and kG. Note that +, k and kG are also associative. Moreover success and f ailure are the identity and the absorbing elements under the parallel composition k, respectively (namely for each agent A, we have that Aksuccess and Akf ailure are the agents A and f ailure, respectively). In the following, we will usually write a tcla process P = C.A as the corresponding agent A, omitting C when not required by the context. hadd(Arg0; R0) ! A; hArg; Rii ! hA; hArg [ Arg0; R [ R00ii
where R00 = f(a; b) 2 R0 j a; b 2 Arg [ Arg0g
Re
Ch (
If (
E1 2 E0; hE2; F i ! hA2; F i ND (
hE1 + E2; F i ! hE10 + E20; F i hA[y=x]; F i ! hA0; F 0i with y 2 U n Arg
h9xA; F i ! hA0; F 0i hp(b; m; ; j); F i ! hA[b=a; m=l; = ; j=i]; F i when p(a; l; ; i) :: A
Suppose we have an agent A whose knowledge base is represented by a framework F = hArg; Ri. An add(Arg0; R0) action performed by the agent results in the addition of a set of arguments Arg0 U (where U is the universe) and a set of relations R0 to the AF F . When performing an addition, (possibly) new arguments are taken from U n Arg. We want to make clear that the tuple (Arg0; R0) is not an AF, indeed it is possible to have Arg0 = ; and R0 6= ;. However, the structure of the shared store after an add operation is guaranteed to be an AF compliant with De nition 1, since only attacks between arguments in Arg [ Args0 are added to R.
Intuitively, rmv(Arg; R) allows to specify arguments and/or attacks to be removed from the knowledge base. The removal of an argument from an AF also involves removing all attack relations outgoing from and incoming to that argument, thus making F preserve the structure of an AF. Trying to remove an argument (or an attack) which does not exist in F will have no consequences.
The testc;t(a; l; ) ! A, tests;t(a; l; ) ! A and checkt(Arg; R) ! A
constructs are explicit timing primitives that allow for the speci cation of timeouts.
In fact, in timed applications often one cannot wait inde nitely for an event.
Thus, a timed language should allow us to specify that, in case a given time
GP (
Pa
ND (
HA PC bound is exceeded (i.e. a timeout occurs), the wait is interrupted and an alternative action is taken.
The operator checkt(Arg0; R0) (rules Ch (
The rules for credulous tests CT (
The operator +P (If (
The guarded parallelism GP (
The remaining operators are classical concurrency compositions: the rule parallelism Pa in Table 4 models the parallel composition operator in terms of maximal parallelism. By transition rules, an agent in a parallel composition obtained through k succeeds only if all the agents succeed. In our implementation of rule Pa, we use (F; F 0; F 00) := (F 0 \ F 00) [ ((F 0 [ F 00) n F ) to handle parallel additions and removals of arguments7. In particular, if an argument a is added and removed at the same moment (e.g., trough the program add(fag; fg) ! success k rmv(fag; fg) ! success), we have two possible outcomes: if a was not 6 Other labelling semantics could be considered where undec arguments are further divided into \don't know" and \don't care" [7]. 7 Union, intersection and di erence between AFs are intended as the union, intersection and di erence of their sets of arguments and attacks, respectively. present in the knowledge base, then the add operation gains priority over the rmv one, since a 2 ((F 0 [ F 00) n F ); on the other hand, when a was already in the shared memory, we have that a 62 ((F 0 [ F 00) n F ), and a is removed.
Any agent composed through + (rules ND (
In the following we provide the de nition for the observables of the language, which considers the traces of successful or failed terminating computations that the agent A can perform for each tcla process P = C.A. Given a transition relation !, we denote by ! its re exive and transitive closure. De nition 8 (Observables for tcla). Let P = C.A be a tcla process. We de ne
Oio(P ) = fF1 fF1
Fn ss j hA; F1i ! hsuccess; Fnig [
Fn j hA; F1i ! hf ailure; Fnig: 4
In the context of argumentation, the possibility to include time in the reasoning processes conducted by intelligent agents allows for modelling dynamic behaviours, such as, for instance, the addition and the removal of information at precise moments from a knowledge base.
Agents using tcla constructs and availability functions in TAFs regulate the existence of arguments in a similar way; in particular, we can imagine each agent having control over an argument of the TAF. This result is showed by providing explicitly a translation from a TAF into a tcla process.
In the following, given I , I is ordered if there is no [t1; t2] 2 I such that t2 < t1 and for each i1; i2 2 I, we have that i1 and i2 are disjoint and non-consecutive. Without loss of generality, we consider only ordered sets of intervals. Moreover, given I 6= ; we denote by f irst(I) = 8( > > ><( >[t; +1) > >:[t1; t2] where [t1; t2] 2 I is such that for each T 0 2 I, where T 0 = [t01; t02] or T 0 = [t01 +1), t1 < t01. Moreover, we denote by continue(I) = I n f irst(I).
Finally, given a 2 Arg and a binary relation R de ned over Arg, we denote by R a = f(a; b) j (a; b) 2 Rg [ f(b; a) j (b; a) 2 Rg. To ease the translation, we j use sleep(t) ! A, with t 0, as a shortcut for (A if t 0 check1(fg; fg) ! (sleep(t The agent sleep(t) ! A, with t 0, executes the check operation for exactly t times and then the agent A is executed. Practically, sleep(t) lets the agent A wait for t instants of time.
In the following we assume that for each [t1; t2] 2 S, t1 > 0.
De nition 9 (Translation). The translation of a TAF hfa1; : : : ; ang; R; Avi is T (hfa1; : : : ; ang; R; Avi) = Tadd(0; a1; Rja1 ; Av(a1))k kTadd(0; an; Rjan ; Av(an)) where and where Tadd(t; a; R; S) = Trmv(t; a; R; S) = 8success > > ><add(fag; R) ! success
t >sleep(tin 1) ! > :> (add(fag; R) ! Trmv(t; a; R; S)) otherwise if S = ; if S = f( 1; +1)g 8success > > ><sleep(tfin
tin) ! > > > : (rmv(fag; fg) !
Tadd(tfin + 1; a; R; continue(S))) otherwise if S = f[t1; +1)g tin = (1 if f irst(S) = ( 1; t2]
t1 if f irst(S) = [t1; t2] or f irst(S) = [t1; +1) and tfin = t2 if f irst(S) = (
1; t2] or f irst(S) = [t1; t2].
Theorem 1. The translation T of a TAF produces a tcla program such that, at any instant of time t > 0, the arguments in the store are all and only the arguments available at t in the original TAF.
Corollary 1. Given a tcla program produced by a translation T of a TAF, the set of arguments in the store accepted with respect to a semantics at a given instant of time t > 0 coincides with the set of extensions identi ed by at moment t on the original TAF .
Example 2. Consider the TAF of Figure 3. By following previous translation
T 0, the availability of its timed arguments for each time instant t > 0 can be
simulated by a tcla process that modi es the store by adding and removing part
of the underlying framework. We use ve agents in parallel (see Table 5), each
of which is in charge of handling one argument of the TAF. Synchronisation
between these agents is provided through the use of sleep constructs that handle
time lapsing. In the initial con guration, the shared memory is empty (F =
hfg; fgi).
sleep(
Timed Abstract Dialectical Frameworks (tADFs) are introduced in [2] to cope with acceptance conditions changing over time. Di erently form TAFs, which extend classical AFs with the notion of time intervals, tADFs use generic statements that subsumes arguments and relations (not only including attacks, but also, for instance, supports). Therefore, tADFs are not suitable for being modelled through tcla processes, which, instead, relies on AFs. 6
In this paper, we introduced tcla, an extension of cla in which time is taken
into account in the form of timeouts on expressions. We used maximal
parallelism to realise simultaneous execution of actions carried forward by di erent
agents. We presented the operational semantics, and showed examples of how
to instantiate TAF by using our language. As future work, we would like to
study time-dependent notions of acceptability. We could introduce operators for
checking if a given argument is acceptable in all (or in some) instants of time.
Quantitative temporal operators could, then, be de ned to check acceptability
only in given intervals. We are also planning to provide a working
implementation of tcla able to aid research and serve for application purposes.
13. Cayrol, C., de Saint-Cyr, F.D., Lagasquie-Schiex, M.: Change in abstract
argumentation frameworks: Adding an argument. J. Artif. Intell. Res. 38, 49{84 (2010),
https://doi.org/10.1613/jair.2965
14. Cobo, M.L., Mart nez, D.C., Simari, G.R.: On admissibility in timed abstract
argumentation frameworks. In: Coelho, H., Studer, R., Wooldridge, M.J. (eds.)
ECAI 2010 - 19th European Conference on Arti cial Intelligence, Lisbon,
Portugal, August 16-20, 2010, Proceedings. Frontiers in Arti cial Intelligence and
Applications, vol. 215, pp. 1007{1008. IOS Press (2010), https://doi.org/10.3233/
978-1-60750-606-5-1007
15. Cobo, M.L., Mart nez, D.C., Simari, G.R.: On semantics in dynamic argumentation
frameworks. In: XVIII Congreso Argentino de Ciencias de la Computacion (2013),
http://sedici.unlp.edu.ar/handle/10915/31428
16. Dung, P.M.: On the acceptability of arguments and its fundamental role in
nonmonotonic reasoning, logic programming and n-person games. Artif. Intell. 77(
Software Eng. 18(
Science, vol. 92. Springer (1980), https://doi.org/10.1007/3-540-10235-3 24. Rotstein, N.D., Moguillansky, M.O., Falappa, M.A., Garc a, A.J., Simari, G.R.: Argument theory change: Revision upon warrant. In: Besnard, P., Doutre, S., Hunter, A. (eds.) Computational Models of Argument: Proceedings of COMMA 2008, Toulouse, France, May 28-30, 2008. Frontiers in Arti cial Intelligence and Applications, vol. 172, pp. 336{347. IOS Press (2008), http://www.booksonline. iospress.nl/Content/View.aspx?piid=9292 25. Saraswat, V.A., Jagadeesan, R., Gupta, V.: Timed default concurrent constraint programming. J. Symb. Comput. 22(5/6), 475{520 (1996), https://doi.org/10. 1006/jsco.1996.0064 26. Saraswat, V.A., Rinard, M.C.: Concurrent constraint programming. In: Allen, F.E. (ed.) Conference Record of the Seventeenth Annual ACM Symposium on Principles of Programming Languages, San Francisco, California, USA, 1990. pp. 232{245. ACM Press (1990), https://doi.org/10.1145/96709.96733