For a given ADF we consider three-valued interpretation v : S 7! ft; f ; ug as well as two-valued interpretation v0 : S 7! ft; f g. The possible three truth values can be ordered via the so-called information order i. The value u (unknown) represents the i-least element and is thus the value with the lowest amount of information. The i-incomparable values t (true) and f (false) contain more information than u, i.e. u i t and u i f . We lift the information order to arbitrary interpretations v and w via v i w if v(s) i w(s) for each node s 2 S. Essential for the understanding of ADFs is the so-called gamma operator. For a given three-valued interpretation v the operator considers any two-valued completion w of it and returns the consensus of these completions via the meet operator ui. We have, t ui f = u and u ui t = u ui f = u. The interpretation u maps any node to u and thus represents the least information interpretation. Definition 2. Given an ADF D = (S; ). We define
D : V3D 7! V3D as
D(v) : S 7! ft; f ; ug with s 7! uifw('s) j w 2 [v]2Dg:
Based on the gamma operator several semantics can be defined. The following well-known representatives, namely admissible, complete, preferred and grounded semantics specify their -interpretations as certain (pre)fixpoints of D. D Definition 3. Given an ADF D = (S; ) and v 2 V3 .
1. v 2 adm(D) iff v 2. v 2 cmp(D) iff v = 3. v 2 prf (D) iff v is 4. v 2 grd (D) iff v is i D(v),
D(v), i-maximal in cmp(D) and i-least in cmp(D).
Example 1. Consider the following situation. It is the middle of the night and one wants to get home (h) as quickly as possible. The only two possibilities to get there are either taking the bus (b) or walking (w). Unluckily, it is not known whether the bus will really run tonight. On the other hand it is important to get a little bit of sleep that night (s), which is only possible if the faster connection with the bus is used. In addition walking is only a preferable option if it is not raining (r), which is luckily the case. The scenario can be formally modeled in the following ADF D = (fb; h; r; s; wg; f b = :w ^ b; h = w _ b; r = ?; s = h ^ b; w = :r ^ :bg). ? r :r ^ :b w :w ^ b
b h w _ b
s h ^ b
In order to use the script one has to edit the variables nodes and
chooseinterpretations. The first variable nodes is a list which consists itself of list elements. Each
of these elements has the form ["n", "'n"] where n represents a node and 'n its
corresponding acceptance condition. Both elements have to be of the type string.
The acceptance condition has to be notated as a logical formula where logical
conjunction is represented as "; ", disjunction via "; " and negation as "#". It is
further possible to use shorthands for true ("!") and false ("?"). Moreover,
parentheses are allowed. The whole process is illustrated in Example 2. The variable
chooseinterpretations is a list specifying the considered semantics. Possible inputs
are "a" for admissible, "p" for preferred, "c" for complete or "g" for grounded
semantics. Every input for this field needs to be of the type string. In addition it is
possible to use the option "tri " enabling the evaluation of formulae w.r.t. Kleene’s
three-valued logic K3. This way of calculation is only correct if all used
acceptance conditions are single-node formulae, i.e. any node appears at most once in
an acceptance condition(cf. [4, Definition 7] for more detailed information).
Example 2. The “getting home” scenario from Example 1 can be entered in the
following way:
1 nodes = [["b","#w,b"],["h","w;b"],["r","?"], \
2 ["s","h,b"],["w","#r,#b"]]
3 chooseinterpretations = ["a","c","p"]
The output is displayed in the following style:
4 [[’r’, [’ False ’], {}], [’b’, [’ not ’, ’w’, ’ and ’,
5 ’b’, ’’], {’b’: [
On the technical side, the input from nodes (Example 2, lines 1–3) is first preprocessed into a customized structure respecting Python syntax (Example 2, lines 4–5). During the translation each element from nodes is transformed into a list. The first element represents the name of the node and the second one its corresponding acceptance condition. The additional third element is a lookup table storing the position of all nodes in the transformed acceptance condition. The aim of this table is to allow a fast replacing of nodes with truth values of a given interpretation during the evaluation step.
For a given ADF D the script generates systematically each three-valued interpretation v and calculates the corresponding D(v). The way how D(v) is computed depends on whether the tri option has been chosen. Anyway, in both cases we use the Python built-in eval function for the evaluation of acceptance conditions. If the tri option is specified the system calculates D(v) via Kleene’s three-valued logic. In this case the values f ; u; t are replaced with 0; 0:5; 1 and the semantics is given via v(A ^ B) = minfv(A); v(B)g; v(A _ B) = maxfv(A); v(B)g and v(:A) = 1 v(B). Without this option the script systematically generates all two-valued completions w of v. Moreover, the evaluation of any acceptance condition w.r.t. w is stored. We mark a node if a completion returns a different value than the stored ones. A marked node will be mapped to u. If all nodes are marked we reached u and the calculation is stopped. If not, all completions are computed and we return the values of the nodes according to its completions.
In the next step we compare v and D(v). For admissible interpretations we
have to check v i D(v) and for complete ones v = D(v) is required. For these
two semantics the workflow and pseudocode are illustrated by the flowchart and
the pseudocode presented in Figure 2. In order to calculate preferred
interpretations we first compute all complete ones. After that each complete
interpretation v is systematically taken and compared with all other complete
interpretations w 2 cmp(D) n fvg. A preferred interpretation is found if v i w is always
false. The calculation of grounded semantics is considerably different. Since D is
i-monotonic and the grounded interpretation is defined as i-least fixpoint we
calculate it via iteratively applying the gamma operator starting from i-least
interpretation u [
ADF D, semantics
Start
In this section we evaluate how much faster ADF semantics can be calculated if the three-valued approach instead of the two-valued completion is used. We therefore wrote a testcase generator creating random instances of ADFs with single-node formulae. The generator works as follows: We fix a set S consisting of n nodes. Regarding the acceptance condition for a single node a we first determine Preprocessing
tri option? yes Use three-valued logic for D(v) Generating v 2 V3D Compute D(v)
Threevalued intepration v0 left? yes no
Use two-valued completions for D(v) Evaluate v and
D(v) w.r.t. no valid interpretations Stop
D(v) else
for D(v) end if Generate three-valued
D interpretations V3 for v in V3D do
Compute D(v)
Evaluate v and end for return valid interpretations
D(v) w.r.t. which nodes of S should occur in its acceptance formula. This happens through simulated coin flips. If a node has been chosen it gets negated with probability of 0:5. The selected nodes are conjoined with conjunction or disjunction, which is again determined through a coin flip. If no nodes are selected at all the acceptance formula is equally likely set to > or ?. This procedure is repeated for every node in S. The calculation was done with a Ryzen 5 3600 CPU possessing 16 GB RAM. In its current version the script does not support multiple threads meaning that the whole computational process was not parallelized.
For any number of nodes between 1 and 10 we generated and evaluated 100 test instances w.r.t. all considered semantics. The results are displayed in Table 1. The column resp. -tri shows the average times (in seconds) for the classical two-valued completion approach or the three-valued logic approach, respectively. The results were rounded to four digits after the decimal point. The raw data can be found at the mentioned github page. The column speed factor shows the proportion from computation time of the two-valued completion to computation time of the three-valued approach. For the admissible and grounded interpretations the computational time is further illustrated in Figure 3. Please note that the y-axis uses logarithmic scale meaning that the growth in time is exponential.
As can be seen for both approaches the grounded semantics are calculated in very short time. For this semantics we start directly with u and apply D repeatedly till a fixpoint is reached. Therefore not every three-valued interpretation has to be generated and evaluated, which increases the speed of computation. In addition for grounded semantics the speed gain w.r.t. the three-valued approach is remarquable. This can be explained because u is the interpretation, which requires the most two-valued completions. The evaluation of these completions is skipped through the use of the three-valued approach. Admissible, preferred and complete semantics are influenced by the tri -option too but it is not comparable with the speed gain in case of grounded semantics. Moreover, the differences in calculation time between the three latter semantics are occurring on the scale of hundreds and thousands of seconds. Note that this observation is independent from the chosen approach. However, this is a bit surprising at least for preferred semantics as it uses the computation of complete semantics as a preprocess. Further experimental studies of this issue will be part of future work. It might be the case that a significant computation differences occurs far beyond the number ten of considered statements. To sum up, the three-valued approach increases the performance in an exponential way for any considered semantics. Nevertheless, except grounded semantics, computing ADFs with more than ten statements seems not to be feasible.
nodes 1 2 3 4 5 6 7 8 9 10
In this paper we introduced a Python script which enables a convenient
calculation of various ADF semantics. Python was choosen because it is a widely used
high-level programming language, which enables an easy implementation and is
therefore well-suited to test the benefits of a three-valued logic approach. Another
system calculating ADFs semantics is DIAMOND [
We thank DFG (406289255) and BMBF (01IS18026B) for funding this work.