Distributed Logic Programming

Distributed Logic Programming Zd ra v k o M a rk o v , C h ris t o D ic h e v Institute of Informatics Bulgarian Academy of Sciences Acad.G.Bonchev St. Block 29A, 1113 So a, Bulgaria 1 Introduction Most of the network models used in AI are just notations (e.g. semantic networks). The real working network systems are mainly connected with Parallel Distributed Processing (PDP), well developed in the eld of numeric computation. Even modern connectionism, which attempts to generalize the PDP paradigm is also based on numeric computation. Opposed to numeric computation are the symbolic approaches in AI - the methods for problem solving, including automatic deduction. There is another research direction integrating both approaches. A considerable part of this research is in the eld of Logic Programming. PARLOG [3], Concurrent Prolog [13] and GHC [16] are typical examples of applying PDP approaches in a pure symbolic eld. However the main purpose of these works is not integrating symbolic and parallel computation in a consistent way, rather improving the eciency of the implementations. An interesting approach is proposed by Jorrand in [5] and in some later works. Logic programs are represented as networks of communicating by uni cation agents working in parallel. This approach preserves the original herbrand semantics of Logic Programs without introducing any additional control means (used in the parallel Prolog implementations). This is a formal and elegant way of introducing a new computational paradigm - computation by communication. However this approach is dicult to implement and use in practice. The present paper describes a PDP approach to Logic Programming. The issue of parallelism is not discussed, rather the emphasize is on the distributedness, which is one of the basic features of the described formalism. The main contribution of this paper is showing a way of implementing logical inference in a network environment, called NetClause language (NCL). The basis of NCL is the network formalism presented in [7], where it was considered as an extension of logic programming. Its applications in the eld of graphical object representation and as a connectionist modeling tool are shown there. In the present paper the interpretation of NCL as a logical reasoning scheme is shown. Various aspects of NCL are also discussed in [9,10,11]. The application of NCL in the eld of natural language processing in discussed in [11,14]. 2 An overview of the Net-Clause Language Syntactically the Net-Clause language (NCL) is an extension of the standard Prolog. Its semantics however is aimed at modeling graph like structures (networks), consisting of nodes and links. The nodes specify procedures unifying terms, and the links are channels along which the terms are propagated. The language is designed for describing distributed computation schemes, without centralized control using uni cation as a basic data processing mechanism. The basic constructors of NCL programs are the net-clauses. A net-clause is a sequence of nodes, syntactically represented as structures (complex terms), separated by the delimiter ":". The network links are implicitly de ned by shared variables among di erent nodes in a net-clause. The variables in NCL are called net-variables. The NCL networks are built out of two types of nodes - free nodes and procedural nodes. The free nodes are structures (in the form of Prolog facts) used to access netvariables, inside and outside the net-clause. The procedural nodes are the active elements in the network. Procedures unifying terms are associated to the procedural nodes. The procedures are activated under certain conditions, de ned locally in each node. Thus the control in NCL is distributed. It is based on the uni cation procedure, which is also the basic data processing mechanism in the language. Since there are no explicit control means in the language the control in NCL is data-driven. Generally when unifying netvariables two possible results can occur: binding net-variables to non-variable terms and sharing net-variables. These possibilities de ne the two control schemes in NCL. Each one of them is speci ed by a particular type of procedural node. We describe brie y only the rst control scheme - spreading activation, since the second one (activation by need) does not relate to the connectionist features of NCL. It is described elsewhere (e.g. [11]) in the framework of default reasoning. 2.1 Spreading Activation in NCL The spreading activation control scheme is de ned by procedural nodes written in the following syntax: node(X1,...,Xn,M,<procedure>). The purpose of the node procedure is to unify terms, particularly to bind variables, which in turn could further propagate both data (terms) and control (activation) among other nodes in the network. The node procedure is also an interface to the Prolog system, which is an environment for NCL, i.e. Prolog built-in procedures and predicates can be called too. M is an integer number and its semantics is to de ne a threshold, determining the amount of data required to activate the procedure. Xi are net-variables which serve as channels for term propagating. They can be used both as excitatory links and as inhibitory links for the activation of the procedure. The excitatory links are represented as simple (ordinary) variables and the inhibitory links are represented as negated variables (written as ~Xi). The procedure is activated if the di erence between the number of the bound simple variables and the number of the bound negated ones is equal to M. When de ning a spreading activation node the condition M>0 is required. This ensures that the procedure can not be activated "by de nition", i.e. at least one variable binding is needed for that purpose. Actually binding a simple variable decrements M, and binding a negated one increments it, thus the procedure is activated when M=0. In such a way M can be used to indicate dynamically the number of bound Xi. To illustrate the features of the spreading activation control scheme let us discuss a simple example. Consider the problem of polyhedron recognition. A solution of this problem in Prolog is described in [7,8]. A polyhedron can be considered as an attributed graph, represented as a list of edges, each one in the following form: edge(Vertex1,Vertex2,Slope,Length) Thus an instance of a parallelogram can be represented by the following list: [edge(1,2,0,20),edge(2,3,30,50),edge(3,4,0,20),edge(4,1,30,50)] An important feature of this representation is the possibility to de ne a class of gures, using variables instead of xed values standing for the vertex names and attributes. Thus the class of all parallelograms is represented as follows: [edge(A,B,S1,L1),edge(B,C,S2,L2),edge(C,D,S1,L1),edge(D,E,S2,L2)] Using variables as edge attributes ensures that the class representation is free of any speci c geometric properties as size, orientation, etc. Using this representation the problem of polyhedron recognition comes to the problem of graph isomorphism. This in turn is solved easily (but not eciently) by a simple recursive predicate, checking whether a list is a sublist of another list. The pure subgraph matching problem is NP-complete. However, in some cases a proper representation may be found to make the graph matching algorithm applicable in practice. The aim is to minimize the number of the backtracking steps occurring in the "bad" ordering combinations. The use of attributes in the graph improves the eciency as it is shown in [8]. However, there is a "second order" problem, which appears where more than one class is used. The overall eciency in such case depends very much on the order of the selected classes to be recognized, since the matchings between the instance and each of the classes is tested sequentially. Yet another disadvantage is that more complex geometric properties (e.g. perpendicularity) cannot be directly represented as graph attributes. Let us discuss now the NCL solution of the above stated problem. Consider the following net-clause program: /* Free Nodes - Network Inputs */ edge(A,B,S1,L1): edge(B,C,S2,L1): edge(C,D,S1,L1): edge(D,A,S2,L1): edge(B,E,S2,L2): edge(E,F,S1,L1): edge(F,A,S2,L2): edge(E,G,S3,L3): edge(G,A,S4,L4): /* General case of a four-side figure */ node(A,B,E,G,4,fig(four_side_figure)): /* Hidden node checking perpendicularity */ node(S1,S2,2,perp(S1,S2,P)): /* Non-perpendicular figures */ node(A,B,E,F,~P,4,fig(parallelogram)): node(A,B,C,D,~P,4,fig(rhombus)): /* Perpendicular figures */ node(A,B,E,F,P,5,fig(rectangular)): node(A,B,C,D,P,5,fig(square)): /* Free Node - Network Output */ fig(Fig). /* Procedure calculating perpendicularity */ perp(X,Y,ok):-0 is (X-Y) mod 90,!. perp(_,_,_). /* 1 */ /* 2 */ /* 3 */ /* 4 */ /* 5 */ /* 6 */ The program describes a network for recognition of planar four-side geometric gures. The gures are represented as a collection of edges with parameters - written as free nodes. The shared variables in these nodes represent the common vertices and the geometric constraints (parallel and same-length edges). The variables, grouped in the spreading activation nodes, represent a "part-of" hierarchy. Thus, unifying the free nodes with the nodes of a particular instance, the bound net-variables activate the corresponding class of gures. The example shows a way of using hidden nodes in such networks. Node 2 is activated when the net-variables S1 and S2 (representing the slopes of the corresponding edges) are bound. If the condition for perpendicularity is present, then the procedure "perp" binds the net-variable P, thus activating the "perpendicular" classes and suppressing the "non-perpendicular" ones (because of the inhibitory link ~P). The network is activated by specifying the edges of sample gures as a net-clause query. The corresponding class is obtained by the free node " g". Some examples of the network activation are shown below: <- edge(1,2,0,20),edge(2,3,45,30),edge(3,4,0,20),edge(4,1,45,30),fig(X). X=parallelogram yes <- edge(1,2,0,20),edge(2,3,90,20),edge(3,4,0,20),edge(4,1,90,20), fig(square). yes <- edge(a,b,0,20),edge(c,d,45,30),edge(d,e,10,40),edge(e,a,50,60),fig(X). X=four_side_figure yes <- edge(a,b,0,20),edge(c,d,45,30),edge(d,e,10,40),edge(e,a,50,60),fig(X). X=four_side_figure 2.2 Lazy Uni cation The basic feature of the net-variable is the property to be single assignment. In the network terminology this means that the net-variable is a channel which can propagate successfully only one item of data (term). Thus the spreading activation node can work only once (not taking into account the alternative solutions). This makes the NCL network in a sense " at", i.e. each net-clause can process only one pattern of data and if we have many of them several copies of the same net-clause are required. This property is typical for connectionism, but it is quite far from the symbolic approaches (e.g. the Prolog clauses are patterns for data processing). To ll the gap a special kind of net-variable is introduced, called lazy net-variable. It realizes the concept of multiple assignment, keeping in the same time the property of logic variable. Two types of lazy net-variables are implemented in NCL. The lazy net-variables of type 1 has three basic features:    The lazy variable is never bound. It only propagates terms to other variables by means of activating procedures in the spreading activation nodes. The uni cation with lazy variables always succeeds. The lazy variables propagates terms only when all its occurrences propagate uni able terms. The lazy net-variables of type 2 has only the last feature. Thus it may be bound and hence its binding may fail. The uni cation involving lazy variables is called lazy uni cation. The implementation of the lazy uni cation is based on the concepts of streams and coroutines borrowed from the lazy evaluation in functional programming [2,4]. The lazy net-variables are speci ed by the procedure lazy(N), where N is the lazy variable type. After specifying the query "<-lazy(N)" the variables of all subsequently loaded in the database net-clauses are of the corresponding type. To illustrate the features of lazy variables (type 1) consider the following example. <- lazy(1). a(X): b(X): node(X,1,(write(X),nl)). <- a(a(1,2)),b(1),b(2),a(f(X)),b(f(z)),b(a(1,Y)),a(2). f(z) a(1,2) 2 X=z Y=2 A natural interpretation of the above net-clause program is a stream one. The above sequence of data represents two streams of terms directed to the free nodes a and b. The net-variable X plays the role of a channel along which the terms from both streams are uni ed. If two terms are uni ed successfully the procedure in the corresponding spreading activation node is activated. The terms can arrive at the free nodes in an arbitrary sequence i.e. not in uni able pairs. So the channel X synchronizes the streams, i.e. performs an incremental communication between them. One step in this incremental process is one uni cation with a free node. A lazy variable can occur in more than two free nodes, i.e. it can synchronize more than two streams. In this case the lazy variable nds the most general uni er (mgu) of the terms from all streams. The implementation of the rst type of the lazy uni cation mechanism is based on the use of a local database. Such database is provided for each free node with lazy variables of type 1. It is a dynamic data structure existing until the net-clause is active. The local database stores all bindings of the variables in a free node for further uni cation with the terms stored in the other local databases. The access to such databases is uniform - storing and retrieving data based only on the uni cation. Here is an example of using lazy variables as a dynamic database: <- lazy(1). a(Key,Data):[]. <- a(1,data1),a(2,data2),a(3,data3), a(2,X),a(1,Y). X=data2 Y=data1 /* Storing data */ /* Accessing data */ The implementation of the lazy net-variables of type 1 based on the stream concept has a disadvantage in respect to some Prolog "classics". This is the possibility to de ne several free nodes with same functors and to use backtracking to access the nodes other than the rst one. This is the case in the geometric gure example from Section 2.1. The sample edges are uni ed with the network inputs due to the backtracking occurring when some net-variables are bound. This is not possible using lazy net-variable of type 1. Actually the concepts of streams and backtracking are counterparts in sense of organization of computational process and hence cannot be combined in a single mechanism. The "backtrackability" of the free nodes can be achieved using lazy net-variables of type 2. They may be bound and hence may cause backtracking. 3 Logical Inference in NCL NCL is a term manipulation language based on uni cation, a common feature of most deductive inference systems. In Section 3.1. an interpretation of a subset of NCL in the framework of data- driven inference (forward chaining) is shown. Furthermore unlike the standard Logic Programming, NCL allows the set of used formulae to be extended to a class of formulae in non-clausal form (shown in Section 3.2). From logical point of view a net-clause is a conjunction of Horn clauses, where the scope of the universal quanti ers is extended to all clauses constituting the net-clause. Thus a net-clause allows communication links to be established between several Horn clauses through the shared variables. Therefore the procedural semantics of NCL can be expressed in terms of nonclausal resolution [12]. Thus considering its logical foundations NCL is an extension of the languages based on SLD-resolution [6]. 3.1 Data-driven inference in NCL In this Section the basic principles of the NCL implementation of data-driven inference in Horn clause logic are described. The further discussion is based on a correspondence between Horn clauses and a subset of net-clauses (excluding default nodes). Generally we have three types of Horn clauses. They can be trans- lated into net-clauses applying the following transformation rules: 1. Each program clause is translated into a net-clause, where the clause head is represented by a spreading activation node and the clause body - by a collection of free nodes. Variables X1,...,Xm are all variables occurring in the subgoals A1,...,Ap. p(Y1,...,Yn) <-- A1,...,Ap <===> node(X1,...,Xm,m,p(Y1,...,Yn): A1: ... Ap. 2. The goal clause is represented as a net-clause built out of free nodes, which can share variables. <-- B1,...,Bn <===> B1:...Bn. 3. The unit clauses are represented as data (NCL query), which activates the net-clause program. Di erent net-clauses communicate through the uni cation between procedural nodes and free nodes, and the whole process is governed by the spreading activation scheme. C1 <-... Cn <-- <===> <- C1,...,Cn. To illustrate the above correspondence let us discuss an example. Consider the following Horn clause program: 1. 2. 3. 4. 5. p(a,b) <-p(c,b) <-p(X,Z) <-- p(X,Y),p(Y,Z) p(X,Y) <-- p(Y,X) <-- p(a,c) (1) Applying the above rules this program is transformed into the following net-clause program (the Horn clauses and net-clauses are numbered correspondingly). 1,2. 3. 4. 5. <- p(a,b),p(c,b). node(X,Y,Z,3,p(X,Z)):p(X,Y):p(Y,Z). node(X,Y,2,p(X,Y)):p(Y,X). p(a,c):[]. (2) Program 1 has clear declarative meaning, however there is no Prolog system, which is able to nd a refutation for it. This is because of the xed computation and search rules used in the practical implementations of the SLD-resolution. Program 2 runs successfully on the net-clause interpreter. It realizes data- driven inference directed from the unit clauses to the goal clause. The refutation tree of the corresponding resolution procedure is shown in Figure 1. It is a kind of resolution where the refutation procedure is initiated by the unit clause resolution. In fact the data, which represent the set of unit positive clauses is the input for the resolution process. So, the data-driven inference can be interpreted in terms of unit resolution [1,15]. ~p(X,Y) v ~p(Y,Z) v p(X,Z) ?? ~p(Y,X) v p(X,Y) ? p(c,b) HH HHH  HHH ??  HH H? ~p(b,Z) v p(a,Z) p(b,c) HH  HHH   H p(a,c) ~p(a,c) HHH    HHH p(a,b) Figure 1. A refutation tree for NCL data-driven resolution Using clauses 1-4 of program 1 non-ground goals could be proved too. For example we can alter the goal clause 5 with the following net-clause: p(X,Y): node(X,Y,2,write(p(X,Y))). In such a way we de ne a node which can indicate the satisfaction of the goal, printing the answer substitutions. Hence we can obtain all possible solutions: <- p(a,b),p(c,b),nl,fail. p(a,c) p(b,c) p(c,b) p(c,a) p(b,a) p(a,b) In the above example we use only ground terms in the unit clauses. This is because non-variable terms are required to activate the spreading activation nodes. However this is not a substantial restriction since any program can be transformed in such a way that the variables in the unit clauses are replaced with non-variables terms including them. The above example outlines only the basic scheme of using net-clauses for deductive inference. In general to implement completely the data-driven inference strategy additional control means are required. These are mechanisms for synchronization and consistency checking of the data activating a spreading activation node. The synchronization problem is the counterpart of the problem of non-determinism in the goal-driven strategy. In the case of data-driven strategy the data (unit clauses) arrive in arbitrary order to unify the negative literals in a program clause. Furthermore several unit clauses can be used to unify one negative literal. This re ects in concurrent calls to the free nodes in the net-clause. The synchronization problem is solved by using lazy net-variables of type 1. In this case all procedures trying to unify a free node form a stream of terms, which eventually may unify its variables. The problem of consistency arises in the presence of shared variables among di erent free nodes. Their bindings should be the same for the uni cation of all literals, where they appear. This property is easily achieved by using lazy net-variables. In such way the shared lazy variables among di erent free nodes in a net-clause assure the consistency of the di erent streams, i.e. they lter the useless resolution steps in a local sense. The lazy uni cation scheme of the data-driven inference is based on the already de ned correspondence between Horn clauses and net-clauses. The only restriction is that all negative literals in the Horn clause program should have unique names. Thus all free nodes will have unique names, which is needed to ensure the access to them. This restriction is not substantial, since it can be avoided by appropriate transformations. Let us consider the following non-deterministic Horn clause program: 1. 2. 3. 4. 5. p(X,Y) a(X,Y) a(1,2) a(2,2) a(1,3) <-- a(X,Y),b(Y) <-- c(X),d(Y) <-<-<-- 6. 7. 8. 9. 10. 11. b(2) <-c(a) <-d(4) <-d(2) <-c(b) <-<-- p(X,Y) The corresponding net-clause program is the following: <- lazy(1). node(X,Y,2,p(X,Y)): a(X,Y): b(Y). /* 1 */ node(X,Y,2,a(X,Y)): c(X): d(Y). /* 2 */ p(X,Y): node(X,Y,2,(write(p(X,Y)),nl)). /* 11 */ <- a(1,2),a(2,2),a(1,3),b(2),c(a),d(4),d(2),c(b). /* 3,4,5,6,7,8,9,10 */ p(1,2) p(2,2) p(a,2) p(b,2) The free node "a(X,Y)" collects several concurrent calls - three from the net-clause query ( a(1,2), a(2,2), a(1,3) ) and three from the node procedure of net-clause 2 ( a(a,3), a(b,2), a(a,2)). The shared variable Y in net-clause 1 lters some of the uni cations checking the consistency between a(X,Y) and b(Y) - both of them should be uni ed with proper data in order to activate procedure "p". The procedure "p" in turn uni es the free node "p", which activates node 11 printing the solutions - the answer substitutions of the goal variables. The lazy uni cation with decentralized control suits well to the data-driven inference adopted here. The shared variable constraints are applied and new data are generated only when "enough" input data are available. In such a way the amount of the output data is reduced to the necessary minimum. Generally the NCL data-driven inference can be viewed as two independent processes:   Local inference of solutions (new data) and propagating them among the net-clauses in the program. This process is governed locally by the spreading activation nodes. Supplying the net-clause program with data and keeping a track of the currently inferred solutions. An important feature of this organization of the inference process is that partial solutions can be inferred. Generally the net-clause data-driven inference is aimed at solving constructive type of problems (how the parts construct the whole, e.g the geometric gure example), opposed to the goal-driven Prolog inference - aimed at solving problems by decomposing them into sub-problems. However it is important to note that since NCL is an extension of Logic Programming it allows both inference schemes to be used in a uniform environment. 3.2 Logical semantics of the spreading activation The data-driven inference on Horn clauses uses a restricted subset of NCL. This is the restriction that a clause should have at most one positive literal, i.e. the corresponding netclause should have at most one spreading activation node. However the net-clause syntax allows several spreading activation nodes in a net-clause. This case can be interpreted in a more general context of rst order language. De nition 1. A net-clause is an universally quanti ed closed formula in the form C1 & C2 &...& Cm, m>=1, where Ci, i=1,2,...,m are Horn-clauses A v ~B1 v ~B2 v...v ~Bn, n>=0. De nition 2. A net-clause program N is a nite set of net-clauses N=N1,N2,...,Nk, where the net-clauses Ni, i=1,2...,k are implicitly conjoined. A special case of a net-clause is the unit clause Ai. The conjunction A1 & A2 &...& An corresponds to the NCL data <- A1,A2,...,An., where Ai, i=1,2,...,n are propositions. The main di erence between Horn clause and net-clause programs is that in net-clause programming variables in di erent Horn clauses are allowed to be shared. To illustrate this let us consider the following example. Suppose we have two Horn clauses de ning two geometric gures (rhombus and parallelogram) by their edges: rhombus(A,B,C,D) <-- edge(A,B,S1,L1),edge(B,C,S2,L1), edge(C,D,S1,L1),edge(D,A,S2,L1). parallelogram(G,H,E,F) <-- edge(E,F,S3,L2),edge(F,G,S4,L3), edge(G,H,S3,L2),edge(H,E,S4,L3). An equivalent expression of the above set of Horn clauses using a traditional logical notation is the following one: ( rhombus(A,B,C,D) v ~edge(A,B,S1,L1) v ~edge(B,C,S2,L1) v ~edge(C,D,S1,L1) v ~edge(D,A,S2,L1) ) & ( parallelogram(G,H,E,F) v ~edge(E,F,S3,L2) v ~edge(F,G,S4,L3) v ~edge(G,H,S3,L2) v ~edge(H,E,S4,L3) ) (1) Taking into account the meaning of the above formula the following substitutions can be performed: s = { G/A, H/B, S3/S1, L2/L1, S4/S2 } Applying s and simplifying the formula we obtain ( rhombus(A,B,C,D) v ~edge(A,B,S1,L1) v ~edge(B,C,S2,L1) v ~edge(C,D,S1,L1) v ~edge(D,A,S2,L1) ( parallelogram(A,B,E,F) v ~edge(E,F,S1,L1) v ~edge(F,A,S2,L3) v ~edge(B,E,S2,L3) ) ) & (2) Formula (2) is an instance of formula (1). Formula (2) represents no longer two separate gures but one joining them together. The geometric meaning of substitutions s is shown in Figure 2. F E







D C

? ? ?? ??



A?? B?? G

H

F E ? ? ? ? ? ? s HH D?? C??  ? ? ?? A?? B?? Figure 2. Formula (2) is not in clausal form and thus cannot be translated back into a set of Horn clauses. However following the de nition 1 formula (2) is a net-clause, which can be written in NCL syntax as: <-lazy(2). edge(A,B,S1,L1): edge(B,C,S2,L1): edge(C,D,S1,L1): edge(D,A,S2,L1): edge(B,E,S2,L3): edge(E,F,S1,L1): edge(F,A,S2,L3): node(A,B,C,D,4,rhombus(A,B,C,D)): node(A,B,E,F,4,parallelogram(A,B,E,F)). The above net-clause can indicate whether a set of edges represents a rhombus or a parallelogram. (Since the edges have all the same names we use the "backtrackable" version of the lazy variables - type 2). The spreading activation scheme realizes a kind of a nonclausal resolution strategy [12], working on rst order formulae in the form of net-clauses. To illustrate this consider the netclauses (Ci are Horn clauses and Di - propositions): (A v ~B1 v ~B2 v...v ~Bm) & C1 & C2 &...& Cn (3.1) D1 & D2 &...& Dk (3.2) Suppose that ~B1 is resolvable with D1. Then applying the non-clausal resolution rule and simplifying the formula by truthfunctional reductions we obtain: ( (A v ~B2 v...v ~Bm) & C1 & C2 &...& Cn )s, (3.3) where s is the mgu applied to resolve ~B1 and D1. Formulae obtained via non-clausal resolution are called derived formulae. Let consider now the general case of non-clausal resolution on net-clauses. Assume that formulae (3.4) and (3.5) are derived at the i-th step of the non-clausal resolution. (C'1 & C'2 & ...& (Ai v ~Bik v...v ~Bim) &...& C'n)s1 (3.4) (A & C1 &...& Cp)s2 (3.5) This means that some of the subformulae occurring in the parent formulae have already been resolved and the corresponding substitutions have been performed. The corresponding sequences of performed substitutions are denoted by s1 and s2. Assuming that (A)s2 is resolvable with (~Bik)s1, and applying the non-clausal resolution rule to formulae (3.4) and (3.5) we obtain (C'1 & C'2 & ...& (Ai v ~Bik+1 v...v ~Bim) &...& C'n)s, where s=s1.s2.s3 is resulting sequence of substitutions and s3 denotes the mgu applied to resolve (A)s2 and (~Bik)s1. The formulae in the form of (3.5) we call assumptions. The above considerations allow us to introduce the following de nition: De nition 3. Let N be a net-clause program and ~G be the goal. The refutation process based on NCL non-clausal resolution is the process of derivation of a sequence of assumptions (A0)s0, (A1)s1,...,(An)sn,<>, where <> denotes a contradiction resulting from the resolution of (An)sn and G. Now we are able to extend the semantics of the data-driven inference. De nition 4. NCL data-driven inference is a restriction of non-clausal resolution that requires at least one of the parent formulae in each non-clausal resolution operation to be a proposition (formula 3.2) or an assumption (formula 3.5). Thus the refutation process in the net-clause language is performed by data-driven inference. Furthermore it can be proved that the NCL data-driven inference strategy is sound and complete. 4 Conclusion In the present paper a network modeling environment called Net-Clause Language (NCL) was described. Besides its original (network modeling) purpose NCL exhibits clear logical semantics. This semantics de nes a framework for using NCL for logical reasoning. Two basic schemes can be used for this purpose - data-driven inference and default reasoning. The data-driven inference was considered as a tool implementing clausal and non-clausal resolution. The default reasoning scheme is discussed in [11], where its application for natural language parsing is shown. An important issue currently focusing our attention is how to program in NCL. Since the language falls in the class of distributed processing ones, programming is considered mostly as learning. A kind of a "learning-from-examples" scheme, based on term generalization is developed. It is considered in the framework of induction of de nite clauses and solves the problem of inducing data-driven rules from their ground instances. This aspect of NCL is reported elsewhere. An important aspect of PDP schemes is parallelism. Though NCL is implemented in a purely sequential environment (extending sequential Prolog) it has some basic features to be implemented on a parallel architecture. Moreover the NCL networks can simulate parallel execution. Generally the functional behavior of parallelism can be achieved in a sequential computational environment when two properties are present: decentralized control and independence of the computation on the order of the input data for each processing element. While the rst condition is an inherent property of NCL, the second one can be achieved by introducing two restrictions:   The use of activation-by-need scheme should be avoided. This scheme exhibits a non-monotonic behavior, which intrinsically depends on the order of the data. The node procedures should not cause side-e ects. Having in hand a distributed computational scheme simulating parallelism, the transition to real parallel processing is only an implementational step. For this purpose it is necessary to assign a separate process to each procedural node in the network. In this scheme the activation conditions can serve as synchronization conditions for the processes. The net-clause networks resemble connectionist networks. The spreading activation nodes can play the role of threshold elements. The typical for connectionism localized and distributed representations are easily achieved in NCL. Thus NCL can be used as a connectionist modeling tool. Moreover it is a step toward integration of connectionist and symbolic approaches to AI. These aspects of NCL are discussed in [7] and elsewhere. References [1] Chang, C.L. and R.C.T. Lee. Symbolic logic and mechanical theorem proving. Academic Press, London, 1973. [2] Friedman, D.P. and D.S. Wise. CONS should not evaluate its arguments, in: S. Michaelson and R.Milner, eds., Automata, Languages and Programming. Edinburgh University Press, 257-284. [3] Gregory, S. Parallel Logic Programming in PARLOG. Addison-Wesley, 1987. [4] Henderson, P. and J.H. Morris. A lazy evaluator, in: Proceedings of the 3rd ACM Symposium on Principles of Programming Languages, 1976, ACM, 95-103. [5] Jorrand, Ph. Design and implementation of a parallel inference machine for rst order logic, in: Proc. PARLE Conference. Lecture Notes in Computer Science No. 259, Springer-Verlag, 1987. [6] Lloyd, J.W. Foundations of Logic Programming. Springer-Verlag, 1984. [7] Markov, Z. A framework for network modeling in Prolog, in: Proceedings of IJCAI-89, Detroit, U.S.A (1989), 78-83. [8] Markov, Z. and Th. Risse. Prolog Based Graph Representation of Polyhedra, in: Proceedings of AIMSA'88, Arti cial Intelligence III, North-Holland, 1988, 187-194. [9] Markov, Z. and Ch. Dichev. Logical inference in a network environment, in: Proceedings of AIMSA'90, Arti cial Intelligence IV, North-Holland, 1990, 169-178. [10] Markov, Z., C. Dichev and L. Sinapova. The Net-Clause Language - a tool for describing network models, in: Proceedings of the Eighth Canadian Conference on AI, Ottawa, Canada, 23-25 May, 1990, 33-39. [11] Markov, Z., L. Sinapova and Ch. Dichev. Default reasoning in a network environment, in: Proceedings of ECAI-90, Stockholm, Sweden, August 6-10, 1990, 431-436. [12] Murray, N.V. Completely non-clausal theorem proving, Arti cial intelligence 18 (1982), 67-85. [13] Shapiro, E. Concurrent PROLOG: A Progress Report, in: Lecture Notes in Computer Science No. 232, Springer-Verlag, 1986, 277-313. [14] Sinapova, L. A network parsing scheme, in: Proceedings of AIMSA'90, Arti cial Intelligence IV, North-Holland, 1990, 383-392. [15] Stickel, E.M. An Introduction to Automated Deduction, in: W. Bibel, Jorrand, eds., Fundamentals of Arti cial Intelligence. An advanced Course, Springer-Verlag, 1986. [16] Ueda, K. Guarded Horn Clauses, ICOT Technical Report TR-103, 1985. View publication stats