Semantics of Deductive Databases in a Membrane Computing Connectionist Model

Semantics of Deductive Databases in a Membrane Computing Connectionist Model Daniel D´ıaz-Pernil1, Miguel A. Guti´errez-Naranjo2 1Research Group on Computational Topology and Applied Mathematics Department of Applied Mathematics - University of Sevilla, 41012, Spain [email protected] 2Research Group on Natural Computing Department of Computer Science and Artificial Intelligence University of Sevilla, 41012, Spain [email protected] Summary. The integration of symbolic reasoning systems based on logic and connectionist systems based on the functioning of living neurons is a vivid research area in computer science. In the literature, one can found many efforts where different reasoning systems based on different logics are linked to classic artificial neural networks. In this paper, we study the relation between the semantics of reasoning systems based on propositional logic and the connectionist model in the framework of membrane computing, namely, spiking neural P systems. We prove that the fixed point semantics of deductive databases and the immediate consequence operator can be implemented in the spiking neural P systems model. 1 Introduction Two of the most well-known paradigms for implementing automated reasoning in machines are, on the one hand, the family of connectionist systems, inspired in the network of biological neurons in a human brain and, on the other hand, logicbased systems, able to represent and reason with well-structured symbolic data. The integration of both paradigms is a vivid area in artificial intelligence (see, e.g., [2, 3, 8]). In the framework of membrane computing, several studies have been presented where P systems are used for representing logic-based information and performing reasoning by the application of bio-inspired rules (see [7, 11]). These papers study approaches based on cell-like models, as P systems with active membranes, and deal with procedural aspects of the computation. The approach in this paper is different in both senses. On the one hand, the connectionist model of P systems is considered, i.e, the model of P system inspired by the neurophysiological behavior of neurons sending 174 D. D´ıaz-Pernil and M.A. Guti´errez-Naranjo electrical impulses along axons to other neurons (the so-called spiking neural P systems, SN P systems for short). On the second hand, we consider the semantics of propositional deductive databases in order to show how SN P systems can deal with logic-based representing and reasoning systems. One of the key points of the integrate-and-fire formal spiking neuron models [6] (and, in particular, of the SN P systems) is the use of the spikes as a support of the information. Such spikes are short electrical pulses (also called action potentials) between neurons and can be observed by placing a fine electrode close to the soma or axon of a neuron. From the theoretical side, it is crucial to consider that all the biological spikes of an alive biological neuron look alike. This means that we can consider a bio-inspired binary code which can be used to formalize logic-based semantics: the emission of one spike will be interpreted as true and the absence of spikes will be interpreted as false. As we will show below, SN P systems suffice for dealing with the semantics of propositional logic systems. The main result of this paper is to prove that given a reasoning system based on propositional logic it is possible to find an SN P system with the same declarative semantics. A declarative semantics for a rule-based propositional system is usually given by selecting models which satisfy certain properties. This choice is often described by an operator mapping interpretations to interpretations. In this paper we consider the so-called immediate consequence operator due to van Emden and Kowalski [5]. It is well-know that such operator is order continuous and its least fix point coincides with the least model of KB. We adapt the definition of the immediate consequence operator to a restricted form of SN P system and we prove that a least fix point, and hence a least model, is obtained for the given reasoning system. The paper is organized as follows: firstly, we recall some aspects about SN P systems and the semantics of deductive databases. In Section 3 we prove that standard SN P systems can deal with the semantics of deductive databases. Finally, some conclusions are provided in the last section. 2 Preliminaries We assume the reader to be familiar with basic elements about membrane computing and the semantics of rule-based systems. Next, we briefly recall some definitions. We refer to [13] for a comprehensive presentation of the former and [1, 4, 12] for the latter. 2.1 Spiking Neural P Systems SN P systems were introduced in [10] with the aim of incorporating in membrane computing ideas specific to spike-based neuron models. It is a class of distributed and parallel computing devices, inspired by the neurophysiological behavior of neurons sending electrical impulses (spikes) along axons to other neurons. Semantics of Deductive Databases . . . 175 In SN P systems the cells (also called neurons) are placed in the nodes of a directed graph, called the synapse graph. The contents of each neuron consist of a number of copies of a single object type, called the spike. Every cell may also contain a number of firing and forgetting rules. Firing rules allow a neuron to send information to other neurons in the form of spikes which are accumulated at the target cell. The applicability of each rule is determined by checking the contents of the neuron against a regular set associated with the rule. In each time unit, if a neuron can use one of its rules, then one of such rules must be used. If two or more rules could be applied, then only one of them is non-deterministically chosen. Thus, the rules are used in the sequential manner in each neuron, but neurons function in parallel with each other. As usually happens in membrane computing, a global clock is assumed, marking the time for the whole system, and hence the functioning of the system is synchronized. Formally, an SN P system of the degree m≥1 is a construct1 Π= (O, σ1, σ2, . . . , σm, syn) where: 1. O={a}is the singleton alphabet (ais called spike); 2. σ1, σ2, . . . , σmare neurons, of the form σi= (ni, Ri), 1 ≤i≤m, where: a) ni≥0 is the initial number of spikes contained in σi; b) Riis a finite set of rules of the following two forms: (1) firing rules E/ap→a, where Eis a regular expression over aand p≥1 is an integer number; (2) forgetting rules as→λ, with san integer number such that s≥1; 3. syn ⊆ {1,2, . . . , m} × {1,2, . . . , m}, with (i, i)6∈ syn for 1 ≤i≤m, is the directed graph of synapses between neurons. The rules of type (1) are firing rules, and they are applied as follows. If the neuron σicontains kspikes, k≥p, and akbelongs to the language L(E) associated to the regular expression E, then the rule E/ap→acan be applied. The application of this rule means removing pspikes (thus only k−premain in σi), the neuron is fired, and it produces one spike which is sent immediately to all neurons σjsuch that (i, j)∈syn. The rules of type (2) are forgetting rules and they are applied as follows: if the neuron σicontains exactly sspikes, then the rule as→λfrom Ri can be used, meaning that all sspikes are removed from σi. If a rule E/ap→aof type (1) has E=ap, then we will write it in the simplified form ap→a. In each time unit, if a neuron σican use one of its rules, then a rule from Rimust be used. Since two firing rules, E1/ap1→aand E2/ap2→acan have L(E1)∩L(E2)6=∅, it is possible that two or more rules can be applied in a neuron, and in that case only one of them is non-deterministically chosen. The j-th configuration of the system is described by a vector Cj= (t1, . . . , tm) where tkrepresents the number of spikes at the neuron σkin such configuration. 1We provide a definition without delays, input or output neurons because these features are not used in this paper. 176 D. D´ıaz-Pernil and M.A. Guti´errez-Naranjo The initial configuration is C0= (n1, n2, . . . , nm). Using the rules as described above, one can define transitions among configurations. Any sequence of transitions starting in the initial configuration is called a computation. A computation halts if it reaches a configuration where no rule can be used. Generally, a computation may not halt. If it halts, the last configuration is called a halting configuration. 2.2 Semantics of Rule-based Deductive Databases Given two pieces of knowledge Vand W, expressed in some language, the rule V→Wis usually considered as a causal relation between Vand W. In this paper, we only consider propositional logic for representing the knowledge. Given a set of propositional variables {p1, . . . , pn}, a rule is a formula B1∧ · · · ∧ Bm→Awhere m≥0, A, B1,...Bmare variables. The variable Ais called the head of the rule and the conjunction of variables B1∧· · ·∧Bmis the body of the rule. If m= 0, it is said that the body of the rule is empty. A finite set of rules KB is a deductive database. An interpretation Iis a mapping from the set of variables {p1, . . . , pn}to the set {0,1}. As usual, we will represent an interpretation Ias a vector (i1, . . . , in) with I(pk) = ik∈ {0,1}for k∈ {1, . . . , n}. The set of all the possible interpretations for a set of nvariables will be denoted by 2n. Given two interpretations I1and I2, I1⊆I2if for all k∈ {1, . . . , n},I1(pk) = 1 implies I2(pk) = 1. We will denote by I∅ the interpretation that maps to 0 every variable, I∅= (0,...,0). The interpretation Iis extended in the usual way, I(B1∧ · · ·∧Bm) = min{I(B1), . . . , I(Bm)}and for a rule2 I(B1∧ · · · ∧ Bm→A) = 0 if I(B1∧ · · · ∧ Bm) = 1 and I(A) = 0 1 otherwise An interpretation Iis a model for a deductive database KB if I(R) = 1 for all R∈KB. Next, we recall the propositional version of the immediate consequence operator which was introduced by van Emden and Kowalski [5]. Definition 1. Let KB be a deductive database on a set of variables {p1, . . . , pn}. The immediate consequence operator of KB is the mapping TKB : 2n→2nsuch that for all interpretation I,TKB(I)is an interpretation TKB(I) : {p1, . . . , p1}→{0,1} such that, for k∈ {1, . . . , n},TKB(I)(pk) = 1 if there exists a rule B1∧· · ·∧Bm→ pkin KB such that I(B1∧ · · · ∧ Bm) = 1; otherwise, TKB(I)(pk)=0. The importance of the immediate consequence operator is shown in the following proposition (see [9]). 2Let us remark that, from the definition, if m= 0, I(B1∧ · · · ∧ Bm) = 1 and, hence, for a rule with an empty body, we have I(→A) = 1 if and only if I(A) = 1. Semantics of Deductive Databases . . . 177 Theorem 1. An interpretation Iis a model of KB if and only if TKB(I)⊆I. Since the image of an interpretation is an interpretation, the immediate consequence operator can be iteratively applied. Definition 2. Let KB be a deductive database and TKB its immediate consequence operator. The mapping TKB ↑:N→2nis defined as follows: TKB ↑0 = I∅and TKB ↑n=TKB ↑(TKB ↑(n−1)) if n > 0. In the limit, it is also considered TKB ↑ω=[ k≥0 TKB ↑k The next theorem is a well-known result which relates the immediate consequence operator with the least model of a deductive database (see [12]). Theorem 2. Let KB be a deductive database. The following results hold •TKB ↑ωis a model of KB •If Iis a model of KB, then TKB ↑ω⊆I Example 1. Let us consider the following knowledge base KB on the set of variables Γ={p1, p2, p3, p4} R1≡ → p1 R2≡p1→p2 R3≡p1∧p2→p3 R4≡p3→p4 R5≡p2→p4 and let us consider the interpretation I:Γ→ {0,1}such that I(p1) = 1, I(p2) = 0, I(p3) = 0 and I(p4) = 0. Such interpretation can be represented as I= (1,0,0,0). The truth assignment of this interpretation to the rules is I(R1) = 1, I(R2) = 0, I(R3) = 1, I(R4) = 1, I(R5) = 1. Since I(R2) = 0, the interpretation Iis not a model for KB. The application of the immediate consequence operator produces TKB(I) = (1,1,0,0). We observe that TKB(I)6⊆ Iand hence, by Th. 1, we can also conclude that Iis not a model for KB. Finally, if we consider I∅= (0,0,0,0), the following interpretations are obtained by the iterative application of the immediate consequence operator TKB ↑0 = I∅= (0,0,0,0) TKB ↑1 = TKB(TKB ↑0) = (1,0,0,0) TKB ↑2 = TKB(TKB ↑1) = (1,1,0,0) TKB ↑3 = TKB(TKB ↑2) = (1,1,1,1) In this case TKB ↑3 is a fix point for the immediate consequence operator and a model for the deductive database KB. 178 D. D´ıaz-Pernil and M.A. Guti´errez-Naranjo 3 Semantics of Deductive Databases with SN P Systems The semantics of deductive databases deals with interpretations, i.e., with mappings from the set of variables into the set {0,1}(which stand for false and true) and try to characterize which of these interpretations make true a whole deductive database which, from the practical side, may contain hundreds of variables and thousand of rules. The immediate consequence operator provides a tool for dealing with this problem and provides a way to characterize such models. In this section we will explore how this problem can be studied in the framework of SN P systems and prove that the immediate consequence operator can be implemented in this model and therefore, membrane computing provides a new theoretical framework for dealing with the semantics of deductive databases. Our main result claims that SN P systems can compute the immediate consequence operator and hence, the least model of a deductive database. Theorem 3. Given a deductive database KB and an interpretation I, a SN P system can be constructed such that (a) It computes the immediate consequence operator TKB(I). (b) It computes the least model for KB in a finite number of steps. Proof. Let us consider a knowledge database KB, let {p1, . . . , pn}be the propositional variables and {r1, . . . , rk}be the rules of KB. Given a variable pi, we will denote by hithe number of rules which have piin the head and given a rule rj, we will denote by bjthe number of variables in its body. The SN P systems of degree 2n+k+ 3 ΠKB = (O, σ1, σ2, . . . , σ2n+k+2, syn) can be constructed as follows: •O={a}; •σj= (0,{a→λ}) for j∈ {1,...n} •σn+j= (ij, Rj), j∈ {1,...n}, where ij=I(pj) and Rjis the set of hjrules Rj={ak→a|k∈ {1, . . . , hj}} •σ2n+j= (0, Rj), j∈ {1,...k}, where Rjis one of the following set of rules •Rj={abj→a}∪{al→λ|l∈ {1, . . . , bj−1} } if bj>0 •Rj={a→a}if bj= 0. For a better understanding, the neurons σ2n+k+1 and σ2n+k+2 will be denoted by σGand σT. •σG= (0,{a→a}) •σT= (1,{a→a}) •syn ={(n+i, i)|i∈ {1, . . . , n}} ∪(n+i, 2n+j)|i∈ {1, . . . , n}, j ∈ {1, . . . , k} and piis a variable in the body of rj ∪(2n+j, n +i)|i∈ {1, . . . , n}, j ∈ {1, . . . , k} and piis the variable in the head of rj Semantics of Deductive Databases . . . 179 ∪ {(G, T),(T, G)} ∪(T, 2n+j)|j∈ {1, . . . , k} and rjis a rule with empty body  Before going on with the proof, let us note that the construction of this SN P system is illustrated in the Example 2. The next remarks will be useful: Remark 1. For all t≥0, in the 2t-th configuration C2tthe neuron σTcontains exactly one spike and the neuron σGdoes not contain spikes. Proof. In the initial configuration C0,σTcontains 1 spike and σGdoes not contain spikes. By induction, let us suppose that in the C2tthe neuron σTcontains exactly one spike and σGdoes not contain spikes. Since the unique incoming synapse in σTcomes from σGand the unique incoming synapse in σGcomes from σTand in both neurons occurs the rule a→a, then in C2t+1 the neuron σGcontains exactly spike and σTdoes not contain spikes and finally, in C2t+2 the neuron σTcontains exactly spike and σGdoes not contain spikes. Remark 2.For all t≥0the following results hold: •For all p∈ {1, . . . , k}the neuron σ2n+pdoes not contain spikes in the configuration C2t •For all q∈ {1, . . . , n}, the neuron σn+qdoes not contain spikes in the configuration C2t+1 Proof. In the initial configuration C0, for all p∈ {1, . . . , k}, the neuron σ2n+p does not contain spikes and each neuron σn+qcontain, at most, one spike. Such spike is consumed by the application of the rule a→aand, since all the neurons with synapse to σn+qdo not contain spikes at C0, we conclude that at the configuration C1, the neurons σn+qdo not contain spikes. By induction, let us suppose that in C2t, for all p∈ {1, . . . , k}, the neuron σ2n+p does not contain spikes and for all q∈ {1, . . . , n}, the neuron σn+qdoes not contain spikes in the configuration C2t+1. According to the construction, the number of incoming synapses in each neuron σ2n+jis bjif bj>1 and 1 if bj= 0. Such synapses come from neurons that send (at most) one spike in each computational step, so in C2t+1, the number of spikes in the neuron σ2n+jis, at most, bjif bj>1 and 1 if bj= 0. All these spikes are consumed by the corresponding rules. Moreover, at C2t+1, all the neurons with outgoing synapses to σ2n+pdo not contain spikes, so we conclude that at C2t+2, for all j∈ {1, . . . , k}, the neuron σ2n+jdoes not contain spikes. We focus now on the neurons σn+qwith q∈ {1, . . . , n}. By induction, we assume that they do not contain spikes in the configuration C2t+1. Each neuron σn+qcan receive at most hq, since there are hqincoming synapses and the corresponding neuron sends, at most, one spike. Hence, at C2t+2,σn+q has, at most, hqspikes. All of them are consumed by the corresponding rule and, since all the neurons which can send spikes to σn+qdo not contain spikes at C2t+2, we conclude that, for all q∈ {1, . . . , n}, the neuron σn+qdoes not contain spikes in the configuration C2t+3. 180 D. D´ıaz-Pernil and M.A. Guti´errez-Naranjo Remark 3. For all q∈ {1, . . . , n}, the neuron σqdoes not contain spikes in the configuration C2t. Proof. The result holds in the initial configuration. For C2twith t > 0 it suffices to check that, as claimed in Remark 2, for all q∈ {1, . . . , n}, the neuron σn+qdoes not contain spikes in the configuration C2t+1 and each σqreceives at most one spike in each computation step from the corresponding σn+q. Therefore, in each configuration C2t+1, each neuron σqcontains, at most, one spike. Since such spike is consumed by the rule a→λand no new spike arrives, then the neuron σqdoes not contain spikes in the configuration C2t. Before going on with the proof, it is necessary to formalize what means that the SN P system computes the immediate consequence operator TKB. Given a deductive database KB on a set of variables {p1, . . . , pn}, an interpretation on KB can be represented as a vector I= (i1, . . . , in) with ij∈ {0,1}for j∈ {1, . . . , n}. Let us consider that such values ij∈ {0,1}represent the number of spikes placed in the corresponding neuron σn+jat the initial3configuration C0. We will consider that the computed output for such interpretation is encoded in the number of spikes in the neurons σ1, . . . , σnin the configuration C3. The main results of the theorem can be obtained from the following technical remark. Remark 4.Let I= (i1, . . . , in)an interpretation for KB and let S= (s1, . . . , sn) be a vector with the following properties. For all j∈ {1, . . . , n} •If ij= 0, then sj= 0. •If ij6= 0, then sj∈ {1, . . . , hj} Let us suppose that at the configuration C2tthe neuron σn+jcontains exactly sjspikes. Then, the interpretation obtained by applying the immediate consequence operator TKB to the interpretation I,TKB(I)is (q1, . . . , qn)where qj, j∈ {1, . . . , n}, is the number of spikes of the neuron σjin the configuration C2t+3. Proof. Firstly, let us consider k∈ {1, . . . , n}and TKB(I)(pk) = 1. Let us prove that at the configuration C2t+3 there is exactly one spike in the neuron σk. If TKB(I)(pk) = 1, then there exists at least one rule rl≡Bd1∧ · · · ∧Bdl→pk in KB such that I(Bd1∧ · · · ∧ Bdl) = 1. Case 1: Let us consider that there is only one such rule rland the body of rlis empty. By construction, the neuron σ2n+lhas only one incoming synapse from neuron σT; the neuron σn+jcontains exactly sjspikes, j∈ {1, . . . , n}and sj∈ {1, . . . , hj}; and according to the previous remarks: •In C2tthe neuron σTcontains exactly one spike. 3With a more complex design of the SN P system, it may be considered that these neurons do not contain spikes at the initial configuration and the vector I= (i1,...,in) is provided as a spike train via an input neuron, but in this paper we have chosen a simpler design and focus on the computation of the immediate consequence operator. An analogous comment fits for the computed output. Semantics of Deductive Databases . . . 181 •For all p∈ {1, . . . , k}the neuron σ2n+pdoes not contain spikes in the configuration C2t •For all q∈ {1, . . . , n}, the neuron σqdoes not contain spikes in the configuration C2t. In these conditions, the corresponding rules in σTand σn+kare fired and in C2t+1, the neuron σ2n+kcontains one spike. In C2t+2, the neuron σn+kcontains one spike and σkdoes not contain spikes. Finally, in the next step σn+ksends one spike to σk, so, in C2t+3,σkcontain one spike. Case 2: Let us now consider that there exists rl≡Bd1∧. . . Bdl→pkin KB such that I(Bd1∧ · · · ∧ Bdl) = 1 and dl>0. We suppose that I(Bd1∧ · · · ∧ Bdl) = 1 and this means that I(Bd1) = · · · =I(Bdl) = 1 and therefore, in C2t, the neuron σn+djcontains sdjspikes, with sdj∈ {1, . . . , hdj}. All these neurons fire the corresponding rule, and σ2n+khas at C2t+1 exactly bkspikes (since all the incoming synapses send the corresponding spike). The rule abk→ais fired and in C2t+2 the neuron σn+kcontains at least one spike. It may have more spikes depending on the existence of other rules with pkin the head, but in any case, the number of spikes is between 1 and hk. The corresponding rule fires and the neuron σkcontains one spike in C2t+3. Finally, we prove the statements claimed by the theorem: (a) The SN P system computes the immediate consequence operator TKB(I). Proof. It is directly obtained from Remark 4. Let us note that one of the possible vectors S= (s1, . . . , sn) obtained from the interpretation Iis exactly the same interpretation I= (i1, . . . , in). If we also consider the case when t= 0, we have proved that from the initial configuration C0where ikrepresents the number of spikes in the neuron σn+k, then the configuration C3encodes TKB(I). (b) The SN P system computes the least model for KB in a finite number of steps. Proof. Let us consider the empty interpretation as the initial one, i.e., TKB ↑0 = I∅. We will prove that (∀z≥1) TKB ↑z=C2z+1[1, . . . , n] where C2z+1[1, . . . , n] is the vector whose components are the spikes on the neurons σ1, . . . , σnin the configuration C2z+1. We will prove it by induction. For z= 1, we have to prove that TKB ↑1 = TKB (TKB ↑0) = TKB (I∅) is the vector whose components are the spikes on the neurons σ1, . . . , σnin the configuration C3. The result holds from Remark 4 and it has been proved in the statement (a) of the theorem. By induction, let us consider now that TKB ↑z=C2z+1[1, . . . , n] holds. As previously stated, this means that in the previous configuration C2zthe spikes in the neurons σn+1, . . . , σ2ncan be represented as a vector S= (s1, . . . , sn) be a vector with the properties claimed in Remark 4, namely, if the neuron σjhas no spikes in C2z+1, then sj= 0 and, if the