Tractable Inquiry in Information-Rich Environments

1 Paraconsistent Nonmonotonic Dialogues

The synergistic effect of collaborating agents is achieved by their proper communication. However, in dynamic and unpredictable environments up-to-date, sure and complete information is hardly obtainable. This leads to conflicts, uncertainty and paracompleteness, particularly when handling information originating from multiple sources of diverse credibility, quality or significance. In this paper we introduce a new approach to logical modeling of conversing agents, which are prepared to handle inconsistency and ignorance.

To this end, a paracomplete and paraconsistent (i.e., tolerating inconsistencies) logic is necessary, supported by two new truth values: unknown (u) and inconsistent (i). In line with other paraconsistent approaches to modeling dialogues [Takahashi and Sawamura, 2004; Prakken, 2010; Black and Hunter, 2009], inconsistency does not trivialize reasoning but is treated as first-class citizen alike true (t) and false (f). In our system the following choices have been made.

• The four-valued logic of [Vit´oria et al., 2009] underpins the solution.
• Unknown or inconsistent conclusions do not enforce termination of the reasoning process.

∗This research is partially supported by Warsaw Center of Mathematics and Computer Science.

• Such conclusions can be handled via lightweight forms of nonmonotonic reasoning.

Entailment in logic amounts to deriving conclusions from theories that can be seen as complex knowledge bases. However, instead of querying arbitrary theories, in order to reduce complexity we tailor them to their tractable versions like specific rule-based systems. Thus, instead of reasoning in logical systems of high complexity, we query paraconsistent knowledge bases. Only recently has a sufficiently expressive tool existed for creating and querying them in polynomial time: 4QL - a DATALOG¬¬-like four-valued rule-based query language. Following this shift in methodology, the contribution of this paper is an implementation of a tractable, paraconsistent and paracomplete multi-party inquiry dialogue suitable for agents situated in information-rich environments. The overall goal of inquiry is to collectively solve a theoretic problem, resulting in the common knowledge about the solution.

Consider a multi-agent system where each swarm agent is specialized in gathering different type of information via a polling system, and a supervisor agent which verifies certain information for the human user. Suppose the human user asks if it is safe to travel to place X (safe(X)?) and none of the agents knows the answer. Engaging in inquiry on the topic safe(X) allows agents to share only the relevant pieces of their (possibly vast) knowledge and collectively arrive at a final recommendation for the human user. Although conflicts may naturally appear on many different levels of such group activity [Dunin-Ke¸plicz et al., 2014], it is not the goal of inquiry but rather persuasion to resolve them.

Unlike the classical case [Walton and Krabbe, 1995], our approach to inquiry permits 4-valued statements. It turns out that the initial valuation of the topic separates Inquiry-What from Inquiry-That. In both cases, several strategies to handle missing and inconsistent information are presented and formally investigated. The final outcomes of such dialogues are compared against the (possibly inconsistent and incomplete) distributed knowledge of the conversing group [Fagin et al., 1995]. In this regard the soundness of a strategy means that whenever a dialogue terminates with a given conclusion, the same result would be obtained by an individual reasoning from the union of all the agents' belief bases. Accordingly, if a solution is obtainable from the union of agents beliefs, an inquiry under a complete strategy will reach it. The main result of this research concerns soundness and completeness of the open-minded inquiry strategy (Theorem 4).

Enriching the modeling perspective allows us to contemplate several new cognitive situations in communication (see e.g., [Dunin-Keplicz et al., 2015]), occurring also in inquiry. Arguably, other normative models of dialogues would benefit from the 4-valued approach.

The paper is structured as follows. First, in Section 2, the notions underpinning our solution are recalled. Section 3 concerns the formalization of inquiry, its strategies and properties. Finally, Section 4 concludes the paper.

2 Language and Implementation Tool

Our formal inquiry dialogue system uses the logical language of [Małuszy´nski and Szałas, 2013; Szałas, 2013; Małuszy´nski and Szałas, 2011]. Agents' informational stance is encoded in the rule-based query language 4QL 1 defined in [Małuszy´nski and Szałas, 2013], further developed in [Szałas, 2013] and based on a 4-valued logic of [Vit´oria et al., 2009]. 4QL allows for negation both in premisses and conclusions of rules. Importantly, negation in the conclusions may lead to inconsistencies. Even though openness of the world is assumed, rules can be used to close the world locally or globally. Below, the formal language underlying 4QL will be briefly introduced.

In what follows all sets are finite except for sets of formulas. We deal with the classical first-order language over a given vocabulary without function symbols. We assume that Const is a fixed set of constants, Var is a fixed set of variables and Rel is a fixed set of relation symbols.

Definition 1 A literal is an expression of the form R(¯ τ) or ¬R(¯ τ), ¯ τ being a sequence of parameters, ¯ τ ∈ (Const ∪ V ar)k , where k is the arity of R ∈ Rel. Ground literals over Const, denoted by G(Const), are literals without variables, with all constants in Const. If ℓ = ¬R(¯ τ) then ¬ℓ def = R(¯ τ ).◁

Though we use classical first-order syntax, the semantics substantially differs from the classical one as truth values t, i, u, f (true, inconsistent, unknown, false) are explicitly present; the semantics is based on sets of ground literals rather than on relational structures. Intuitively:

• a is t if all sources claim a,
• a is f if all sources claim¬a,
• a is u if no sources claim a nor ¬a,
• a is i if some sources claim a, other claim¬a.

For semantics of propositional connectives see Table 1. The definitions of ∧ and ∨ reflect minimum and maximum with respect to the truth ordering

Whenever truth values are restricted to {f, t}, the semantics is compatible with the semantics of classical first-order logic.

Let v : Var → Const be a valuation of variables. For a literal ℓ, by ℓ(v) we mean the ground literal obtained from ℓ by substituting each variable x occurring in ℓ by constant v(x).

1 Open-source implementation of 4QL is available at 4ql.org.

◁

For a formula α(x) with a free variable x and c ∈ Const, by α(x)xc we understand the formula obtained from α by substituting all free occurrences of x by c. Definition 2 is extended to all formulas in Table 2, where α denotes a first-order formula, v is a valuation of variables, L is a set of ground literals, and the semantics of propositional connectives appearing at righthand sides of equivalences is given in Table 1.

Table 2: Semantics of first-order formulas.

• if α is a literal then α(L, v) is defined in Definition 2;
• (¬α)(L, v) def = ¬(α(L, v));
• (α ◦ β)(L, v) def = α(L, v) ◦ β(L, v), where ◦∈{∨, ∧, →};
• (∀xα(x))(L, v) = min a∈Const (αx a )(L, v),

where min is the minimum w.r.t. ordering (1);

• (∃xα(x))(L, v) = max a∈Const (αx a )(L, v),

where max is the maximum w.r.t. ordering (1).

In 4QL beliefs are distributed among modules. Each module can be treated as a finite set of literals. For specifying rules, multisource formulas and querying modules, we apply the language of [Szałas, 2013].

Definition 3 A multisource formula is an expression of the form: m.A or m.A∈T , where:

• m is a module name;
• A is a first-order or a multisource formula;
• v is a valuation;
• T ⊆ {t, i, u, f}.

We write m.A = v (respectively, m.A ̸= v) to stand for m.A∈{v} (respectively, m.A̸∈{v}). ◁

The intuitive meaning of a multisource formula m.A is:

"return the answer to query expressed by formula A, computed within the context of module m".

The value of 'm.A ∈ T ' is:

{ t when the truth value of A in m is in the set T; f otherwise.

Let A(X1, . . . ,Xk) be a multisource formula with X1, . . . ,Xk being its all free variables and D be a finite set of literals (a belief base). Then A, understood as a query, returns tuples 〈d1, . . . , dk, tv〉, where d1, . . . , dk are database domain elements and the value of A(d1, . . . , dk) in D is tv.

From now on we assume that the domain and language are fixed and the programs and rules are ground. If S is a set, then FIN(S) represents the set of all finite subsets of S. In what follows let C def = FIN(G(Const)) be the set of all finite sets of ground literals over constants in Const.

Definition 4

• Rules are expressions of the form:

where the conclusion ℓ is a positive or negative literal and the premisses b11, . . . , b1i1 , . . . , bm1, . . . , bmim are multisource formulas and ',' and '|' abbreviate conjunction and disjunction, respectively.

• A fact is a rule with empty premisses (evaluated to t).
• A module is a syntactic entity encapsulating a finite number of facts and rules.
• A 4QL program is a set of modules, without cyclic references to modules involving multisource formulas of the form m.A∈T . ◁

If δ is a rule, by head(δ) we mean the rule conclusion. If δ is a fact, head(δ) = δ.

The key concepts of modules and multisource formulas allow us to deal with unknown or inconsistent conclusions without enforcing termination of the reasoning process. Technically, any literal l corresponds to a multisource formula M.l, thus l ∈M.

The semantics of 4QL is defined by well-supported models [Małuszy´nski and Szałas, 2013; Szałas, 2013], i.e., models consisting of (positive or negative) ground literals, where each literal is a conclusion of a derivation starting from facts. For any set of rules, such a model is uniquely determined and computable in deterministic polynomial time O(N k ) where N is the size of domain and k = max(s, t) where s is the maximal arity of relations and t is the maximum number of free variables. As we deal with ground programs, t = 0. When s is a bound constant, which is the case in practical applications of 4QL (qualitative not quantitative reasoning), we achieve tractability. Notice that it is the same complexity as SQL with recursion.

Definition 5 Let P be a 4QL program, A a formula, andMP the well-supported (unique) model of P. Then: P |= A iff for any valuation v we haveMP |= v(A).

As an example, consider program P = {top, su} consisting of two modules top and su (for surveillance).

The literals s, b, h represent suspect, building and hostage, respectively. The program uniquely determines the following well-supported model for module su:

and the following well-supported model for module top:

Definition 6 Let ℓ be a literal and P a 4QL program. A derivation of ℓ from P is the well-supported model MP .

A dependence set of a literal ℓ from a program P consists of literals reachable via backward chaining on P from ℓ.

Definition 7 Let ℓ be a literal and P a 4QL program. A dependence set of ℓ from P, denoted DP,ℓ is a set of literals such that:

• ¬ℓ, ℓ ∈ DP,ℓ,
• if there is a rule ℓ′ :- b11, . . . , b1i1 | . . . | bm1, . . . , bmim in P, such that ℓ′ ∈ DP,ℓ then ∀j∈1..m∀k∈1..ij bjk, ¬bjk ∈ DP,ℓ. ◁

A proof of a literal ℓ from a program P is a subprogram S of P generated from the dependence set DP,ℓ by taking all rules and facts of P whose conclusions are in DP,ℓ.

Definition 8 Let ℓ be a literal, P a 4QL program. A proof of l from P is a 4QL program S ⊆ P such that δ ∈ S iff head(δ) ∈ DP,ℓ, where δ is a fact or a rule. The size of the proof S is the size of the program S. The size of domain of the proof S is the size of the dependence set DP,ℓ. ◁

In order to implement dialogues, the functionality of adding a rule to a 4QL program is required.

Definition 9 We define an operation of adding a ground rule Mi.ℓ :- b to a 4QL program P = {M1, ...,Mn} as follows:

P ′ = P ∪ {Mi.ℓ :- b} =

3 Inquiry

The purpose of inquiry is to collectively solve a theoretical problem [Walton and Krabbe, 1995]. In multi-agent systems, inquiry "starts when some agents are ignorant about the solution to some question or open problem. The main goal is the growth of knowledge, leading to agreement about the conclusive answer of the question. This goal may be attained in many different ways, including an incremental process of argument which builds on established facts in drawing conclusions beyond a reasonable doubt. Both information retrieval and reasoning may be intensively used in this process" [Dunin-Ke¸plicz and Verbrugge, 2010]. In its classical form, inquiry seeks to prove a statement as true or false:

• I1. is(suspect, guilty) = t: 'prove that suspect is guilty',
• I2. is(suspect, guilty) = f: 'prove that suspect is not guilty'.

Our paraconsistent and paracomplete framework allows for contemplating other possibilities:

• I3. is(suspect, guilty) = i: 'prove that there are inconsistent information concerning suspect's guilt',
• I4. is(suspect, guilty) = u: 'is suspect guilty?'.

Specifically (3) exemplifies that inquiry can commence when the goal's initial valuation is i. Our approach allows to model such situations, common in practical applications. In contrast, until a valuation for (4) is established, no classical inquiry on this subject (finding a proof) can commence. This scenario resembles discovery dialogue, where "we want to discover something not previously known" [McBurney and Parsons, 2001]. In our setting, the dialogue aiming at discovering the value of a statement is just another variation of inquiry, so is structured exactly the same. Thus, two types of inquiry dialogues are distinguished:

1. Inquiry-WHAT, where initial valuation of s is u and the goal of the dialogue is to establish the valuation vf of s (see I4).
2. Inquiry-THAT, where initial valuation of s is t, f or i, and the goal of the dialogue is to confirm or refute this by providing the proof for s (see I1, I2, I3).

Inquiry-WHAT succeeds if the final valuation vf ̸= u and Inquiry-THAT succeeds if vf is equal to the initial valuation vi of s. An outcome of a successful inquiry is the valuation of the goal and the proof of it (see Definiton 13).

3.1 Query and Commitment Stores

A common approach to modeling inquiry is to keep two stores (see e.g., [Black and Hunter, 2009; Singh, 1998] and references therein): a Commitment Store (CS), reflecting agents' commitments, and a Query Store (QS), reflecting current open questions. Commitment Store is thus associated with an individual agent while Query Store - with the dialogue.

We maintain both stores associated with the dialogue (CSd,QSd) without any assumptions about agents' individual Commitment Stores. Technically, our Commitment Store reflects the current accumulated knowledge base. It is created empty when the dialogue begins (as no locutions have been uttered yet) and updated with every assertion relevant to the dialogue. To sum up, in our methodology, the inquiry Commitment Store is just an evolving 4QL program (see also [Alferes et al., 2002]).

We assume that in the course of dialogue agents assert only relevant information, that is, rules whose conclusions match the current entries in QS. For a literal l ∈ QS, relevant responses include both l :- b and ¬l :- b (or ℓ and ¬ℓ). Accordingly, two locutions crucial to inquiry are:

• assert(Si, δ, d): agent Si asserts a rule or a fact δ in the dialogue d. If assertion is relevant, it's content is added to CSd and its premisses are added to QSd.
• requestAll(Si, d): agent Si requests content of QSd.

Backward chaining mechanism employed here is commonly used in deductive argumentation for driving the argumentation process (see e.g., [Besnard and Hunter, 2008; Black and Hunter, 2009; Prakken, 2010]).

Definition 10 Locution mt is relevant to an inquiry d at time t iff mt = assert(S,Mi.ℓ :- b, d) and (¬)Mi.ℓ ∈ QStd , where QStd is the Query Store of d at time t. We will alternate between the notions of locution, message, move and utterance. ◁

To make the communication more flexible, the assumption about relevance of the locutions can be realized by a filtering mechanism. Then, instead of requiring that agents make specific moves, we allow them to utter any locutions, filtering out the irrelevant ones 2 .

Definition 11 Commitment Store of a dialogue d at time t is a 4QL program denoted as CStd = 〈M t 1 , . . . ,M tk 〉:

• CS0 d = ∅
• CStd = CSt-1 d ∪ {Mi.ℓ :- b}, such that mt = assert(S,Mi.ℓ :- b, d) is relevant to d at time t,

Next, the Query Store, is a repository of active, unresolved leads in the inquiry. It contains literals which compose the proof of the inquiry goal s. At the beginning the Query Store contains s as a single entry. The mechanism of updating QS is in fact a paraconsistent and paracomplete distributed version of backward chaining 3 , as discussed in Section 3.3. However, in contrast to the classical backward chaining, here we have a number of additional options to investigate. Consequently, there may be various policies for adding literals to QS (selecting threads to follow) and removing them from QS (closing explored threads). Functions open and close (see Definition 12) correspond to such methods.

Definition 12 Let:

• CStd be the Commitment Store of dialogue d at time t,
• mt be the message received at time t,
• close : FIN(C) × FIN(C) → FIN(C) be a method for removing entries from the Query Store,
• open : FIN(C) × FIN(C) → FIN(C) be a method for adding entries to Query Store.

Then, Query Store of an inquiry dialogue d on subject s at time t is a finite set of literals denoted as QStd such that:

2 Such a filter is easy to implement: upon receiving a message, QS is inspected to verify if the rule head is in the scope of inquiry.

3 Hybrid backward-forward chaining techniques may be used if assert locution contains a set of rules, e.g., a subset of proof constructed bottom-up. This is a topic for future research.

• QStd = QSt-1

3.2 Dialogue Outcome vs. Distributed Knowledge

Our setting consists of a finite set of n cooperative agents. The assumption that agents do not withhold information implicitly constraints the number of requestAll locutions per one assertion. Agents' belief bases are encoded as finite, ground 4QL programs P1, . . . , Pn, that share a common ontology and do not change during the course of dialogue. Agents communicate one-to-all without coordination. The wellsupported models MP1 , . . . ,MPn of the programs express agents' final beliefs. The union of individual agents' belief bases (i.e., their distributed knowledge [Fagin et al., 1995]) is expressed by the sum of their 4QL programs: ⋃i∈1..n Pi. An agent can join and leave a dialogue at any time if in between join and leave locutions it utters at least one assertion. Agents cannot repeat assertions. These assumptions allow us to verify quality and completeness of the obtained results.

Since 4QL programs are finite and agents cannot repeat utterances, there must be a moment t when no agent has anything more to utter because either it has run out of relevant moves or because the dialogue goal s has been achieved, whichever comes first. Thus, dialogue terminates at time t. The knowledge accumulated in the course of a dialogue d is expressed by the Commitment Store of that dialogue at termination time t: CStd . The final conclusion depends on the dialogue strategy (see below) and is expressed as follows.

Definition 13 For an inquiry terminating at time t, with the goal s of initial valuation vi, the value of the dialogue conclusion is vf = v(s,MCStd ), whereMCStd is the well-supported model of CStd . Dialogue is:

• successful iff

• unsuccessful otherwise.

◁

The value of the goal s obtained from the union of agents' programs is expressed as v(s,M⋃i∈1..n Pi ).

Definition 14 Let:

• open : FIN(C) × FIN(C) → FIN(C),
• close : FIN(C) × FIN(C) → FIN(C)

be two methods for adding and removing entries to Query Store of dialogue d. Then: ST = 〈open, close〉 is a strategy.

Definition 15 A strategy ST is sound iff whenever dialogue d on subject s conducted under this strategy terminates at t with conclusion k, then if v(s,MCStd ) = k then v(s, M⋃i∈1..n Pi ) = k.

Definition 16 A strategy ST is complete iff whenever dialogue d on subject s conducted under this strategy terminates at t with conclusion k, then if v(s,M⋃i∈1..n Pi ) = k then v(s,MCStd ) = k.

3.3 Opening and Closing Inquiry Threads

In classical backward chaining, the inference engine selects rules whose consequents match the goal to be proved. If the antecedent of the rule is not known to be true, then it is added to the list of goals. In our paraconsistent and nonmonotonic distributed version of backward chaining, the conditions under which antecedent can be added to the list of goals differ depending on the method used. Consequently, there may be various policies for adding literals to QS (selecting threads to follow via function open). From a variety of possibilities, here we investigate two such methods. A literal can be added to the Query Store if:

• A1. Its valuation in the CS model is u, meaning that only threads lacking any evidence whatsoever are explored.
• A2. Always, meaning that every premise is investigated further, even one that is tentatively assumed to be t, f or i.

Definition 17 Let CStd be the Commitment Store of an inquiry dialogue d at time t and MCStd be its wellsupported model. Let mt = assert(S,Mi.ℓ :- b, d) be the message received at time t, such that: b = b11, . . . , b1i1 | . . . | bm1, . . . , bmim . Then,

Notice that in the nonmonotonic paraconsistent backwardchaining, obtaining a truth value for p does not necessarily close the line of reasoning about p, since the evidence put forward by other agents may change the value of p in a number of ways. This is why we conduct inquiry until all relevant information is shared by the agents.

The conditions under which a goal can be abandoned also differ depending on the policy employed. We distinguish two methods for removing literals from QS (closing explored threads via function close):

• R1. Once its valuation in the CS model is not u, meaning that a thread is terminated whenever any evidence for it is found. In some cases it may be closed prematurely, without exposing other evidence relevant to the thread.
• R2. Never, meaning the threads are never abandoned, as the information regarding themmay grow. This will not lead to infinite dialogues, since agents cannot repeat utterances and their programs do not change during dialogue.

Definition 18 Let CStd be the Commitment Store of an inquiry dialogue d at time t and MCStd be its well-supported model. Let QSt-1 d be the Query Store of an inquiry dialogue d at time t - 1 and MQSt-1 d be its well-supported model. Then,

3.4 Inquiry Strategies

The ensuing question is which combination of methods for updating QS makes sense (see Table 3) and how do resulting inquiry strategies differ. Unlike other approaches, we do not assume that the distributed knowledge of the group is complete. If the statement s cannot be proved by agents, the conclusion would simply be u.

Theorem 1 Narrow-minded strategy is neither sound nor complete. Moreover, it is type 1 nondeterministic. 4

Proof. Due to the non-monotonicity of our inquiry, applying the narrow-minded strategy may result in overlooking some important information. As the counterexample, assume three agents A1,A2,A3 are engaged in an inquiry dialogue with the goal enter(b). Their programs are shown in Table 4 and the dialogue conduct is presented in Table 5.

For brevity, we denote assertions in Table 5 as Aj(k), standing for the k-th rule of agent Aj. Dialogue terminates in step 4, since only agent A1 has a rule with conclusion enter(b) but it has already uttered it. Notice that at timepoint t = 2 we had to remove isAt(s, b) from the Query Store, as it became true in MCS2 d . Therefore, agent A1 didn't have a chance to use rule (3) in the dialogue. Obviously, v(enter(b),MCS4 d ) = u, whereas the conclusion obtained by merging agents' programs is v(enter(b),M⋃i∈1..3 Pi ) = t. If instead in the timepoint t = 2 agent A1 would have uttered rule (3), then Query Store and in consequence, the whole dialogue, would look differently, leading to a true conclusion even if agent A1 didn't have a chance to utter rule (1). ◁

4 Type 1 nondeterminism in logic programs means freedom to choose the rule to apply [Sch¨oning, 2008].

Two strategies are equal if the dialogues conducted under these strategies cannot be distinguished on the basis of the content of the stores at any time.

Definition 19 Dialogue D1 is equal to dialogue D2 iff for all finite sequences of moves s = m1 , . . . ,mts , s.t. mi is relevant at i to D1 and to D2, we have that ∀i ∈ 1..ts CSiD1 = CSiD2 and QSiD1 = QSiD2 .

Strategies S1 and S2 are equal iff dialogues conducted under these strategies are equal. ◁

Theorem 2 Forgetful and narrow-minded strategies are equal.

Proof sketch. In the forgetful strategy, we add all literals from the rule body to QS only to remove the known ones afterwards. Therefore, what remains are the unknown literals. Since agents cannot query QS in between adding and removing literals (in theory update of QS is atomic operation), these two strategies are indistinguishable. ◁

Theorem 3 Pragmatic and open-minded strategies are equal in terms of dialogue conduct.

Proof. Let's consider the pragmatic strategy and a goal s. In the first step, the rule s :- b is considered. All rule premisses (b) are either empty (when s is a fact) or unknown (since CS0 is empty). Therefore, in the first step all premisses (b) are added to QS0 and the initial rule s :- b (or fact s) is added to CS0 . Obviously for a literal to be t, f or i, it has to be a rule conclusion or a fact. Since only rules, whose conclusions are in QS are admitted to CS, there cannot be a t, f or i literal which is in CS but was not in QS beforehand. ◁

Theorem 4 Open-minded strategy is sound and complete.

Proof sketch. Assume that v(s,MCStd ) = k and v(s,M⋃i∈1..n Pi ) ̸= k. At the time of dialogue termination, CS contains all relevant messages. Each of these was uttered by at most one agent. Therefore, we can assign each message to a set CSi where i was the sender. Obviously, CSi ⊆ Pi. Therefore we have: CS = ⋃i∈1..n CSi ⊆ ⋃i∈1..n Pi. Since v(s,MCStd ) = k and v(s,M⋃i∈1..n Pi ) ̸= k, that means that there is a part

of the union of programs S def = ⋃i∈1..n Pi \ CS, such that, adding S to CS would change the valuation of s. However, that would mean that there exists a rule (or a fact) in S whose conclusion is in premisses of CS. That means, that rule is a part of the proof for s but was not uttered by the agent, which contradicts our assumptions.

Proof of completeness is analogous.

◁

Notice that in open-minded inquiry on subject s, CS is the evolving proof of s from ⋃i∈1..n Pi and QS is the evolving dependence set of s from ⋃i∈1..n Pi.

3.5 Complexity

Complexity measures of proposed inquiry strategies include:

• communication complexity, concerning only the amount of communication among agents (who have unlimited computational power) [Kushilevitz and Nisan, 1997],
• computational complexity (data complexity), concerning the amount of computation (when communication is free) required to:
• achieve dialogue termination,
• obtain a conclusion of a terminated dialogue.

Computational complexity of both problems is expressed in terms of data complexity [Vardi, 1982; Papadimitriou and Mihalis, 1997], i.e., complexity of evaluating a fixed query (here: inquiry goal) on an arbitrary database (CS). Thus data complexity is given as a function of the size of CS.

In what follows we deal with terminated dialogues and thus we write CS and QS instead of CStd and QStd , respectively. Since open-minded strategy subsumes narrow-minded (Theorems 1 and 4), the (pessimistic) communication complexity results of open-minded strategy hold for both (see Table 6).

Theorem 5 If the size of the domain of the proof of s is N, then the size |QS| of the Query Store at the end of the openminded inquiry is N/2 ≤ |QS| ≤ N.

Proof. Since all literals from rule bodies are added to QS and they are never removed fromQS, in fact they all take part in proving the goal s. Moreover, negative and positive literals from the proof are added to QS only once (either l or ¬l). ◁

Theorem 4 allows us to conclude:

Theorem 6 If the size of the proof of s is M, then the size |CS| of the Commitment Store at the end of the open-minded inquiry is |CS| =M.

Proof. The total amount of information shared by all assert locutions (ai denotes number of assertions by agent i) uttered in the dialogue is:

◁

Recall that n denotes the total number of agents, each holding a certain amount of (relevant) information, such that the proof of the inquiry topic from the union of all agents' belief bases is of size M (from Theorem 6). The communication complexity is polynomial in the total amount of information relevant to the proof.

Theorem 7 Communication complexity of inquiry is O(nM).

Proof. In general there can be up to n-1 requests per one assert. Thus, there can be at most M asserts (agents cannot repeat assertions), M × (n - 1) requests and at most 2 join and leave locutions per one assert. Altogether (n+2)×M locutions exchanged before dialogue termination 5 . Therefore the communication complexity is O(nM). ◁

5 Notice that even for hybrid forward-backward chaining, this is the pessimistic time complexity.

Recall that the size of the domain of the proof is N, which is the upper limit on the size of Query Store (see Theorem 5).

Theorem 8 Computational complexity of a narrow-minded inquiry is: M × O(N k ).

Proof. In the narrow-minded strategy, after each assert the well-supported model of the CS has to be computed, which is in O(N k ) (see Section 2). Thus each such step takes O(N k ). However, at the termination time, the conclusion is known (obtainable in O(1)). Computational complexity of narrowminded inquiry is thus M ×O(N k ). ◁

Theorem 9 Computational complexity of termination of open-minded inquiry is: O(1).

Proof. Handling each assert amounts to adding a rule to CSt , which is in O(1). Handling each request is in O(1) as it amounts to sending the whole QSt back to the agent. ◁

Theorem 9 shows that the major factor in the complexity of the termination problem of the open-minded inquiry is the communication complexity.

Theorem 10 Obtaining the conclusion of a terminated openminded inquiry is O(N k ).

Proof. Recall that computing the well-supported model of CS is in O(N k ), where N is the size of domain. For openminded strategy the computation of the well-supported model is only needed after the dialogue terminates, i.e., once per dialogue. ◁

4 RelatedWork and Conclusions

Exploring paraconsistency and paracompleteness in argumentation is not new: there is a number of formalisms that do not trivialize when inconsistent premises (for a survey see [Walton et al., 2008; Besnard and Hunter, 2008]). In [Black and Hunter, 2009] a formal bi-party inquiry dialog system is proposed where DeLP is used to deal with ignorance and inconsistency. In [Takahashi and Sawamura, 2004] the logic of multi-valued argumentation (LMA) is used and agents can argue using multi-valued knowledge base. In [Prakken, 2010] ASPIC+, a framework for structured argumentation with possible inconsistent knowledge bases and defeasible rules is given. However, none of these formalisms handles inconsistency and ignorance the way 4QL does. Usually the inconsistent premisses yield conclusions (e.g., 'undecided') which cannot be further dealt with.

As indicated in [Dignum and Vreeswijk, 2003; Traum, 2004], several new issues arise when contemplating the plurality of dialogue participants. Multi-party issues were also studied in [Yuan et al., 2011], where a distributed argumentation system was given together with a multi-party dialogue game for computing the defensibility of an argument from consistent knowledge bases. In [Vreeswijk and Hulstijn, 2004], a simple multi-party inquiry dialogue assumed communication in turns with no termination criterion.

Leaving behind the realm of two-valued logical approaches to bi-party dialogues, we arrived at a solution for multi-party, paraconsistent and paracomplete inquiry. We investigated four inquiry strategies, conditional on different policies for opening and closing threads. The relevant results were evaluated against the paraconsistent and paracomplete distributed knowledge of the group.

The general outcome of our research calls for reconsidering normative models of dialogues by introducing two additional logical values: i and u. Specifically, the novelty lies in understanding the very nature of the dialogue's goal, leading to a better discernment between inquiry and discovery and more applications of inquiry.

In future work, we intend to investigate hybrid forwardbackward chaining techniques for a dialogue system, where the locutions can contain a set of rules. Next, we plan to research methods for handling inconsistencies and uncertainty in the Commitment Store via a challenge locution.

5 Acknowledgments

The authors would like to thank Andrzej Szałas for his comments which greatly improved this paper.