Implementation of an executable graphical representation of GAPs
Contents
1. efty ie s Chird STRING DEFAULT PE jelty amp Filles A E ps fees iFrad tt r Z ee CPlies STRING DEFAULT gt ee ee TI Figure 2 Screendump of the GAPCAD user interface with a well known problem The current tokens in place flies are shown at the right bottom At the top a control panel presents the features described in the text GAPCAD offers the following features e One can draw a Petri net and save it as a kind of painting or load a GAP program 4 GAPCAD ARCHITECTURE 18 in DAEDALUS syntax In the latter case the net is automatically being drawn in the window as a Petri net Guards need not be typed They are automatically derived from the arc labels e After finishing the drawing the graph needs to be compiled into the internal extended Petri net structure Syntax errors are located e After compiling one can start the bottom up procedure described in chapter 3 start DAEDALUS assuming a query transitions without outgoing arcs was entered save the net as a GAP in DAEDALUS syntax e During the bottom up procedure every firing transition highlights the tokens in any place are shown if requested a transition can manually be forced to fire e The features of the graph editor are preserved See the GAPCAD manual included in the distribution for detailed descriptions i Gapcad Extensions GraphEd Frames Menus etc gapcad2ui ui2gapcad2. 0 5 2 qla 0 6 3 r X V pla V A q X V A q a 0 3 4 r X j 0 2 X 5 0 V Vo X V V3 4 a 0 6 ew gt k jn Va gt 0 3 V gt 02 In the following a substitution is written as a set of bindings of the form X t where X is a variable and is a term of appropriate colour In example 3 the answering of the query r X 0 2 can be modelled by a firing sequence 1 2 3 4 Transitions 1 and 2 are always enabled since their guards are true and no variable binding is necessary Their firing places the token a 0 5 in p and a 0 6 in q Consider now transition 3 A possible substitution is V 0 5 V2 0 6 V3 0 6 X a Due to the fact that the guard V3 gt 0 3 evaluates to true under g transition 3 is enabled Its firing see below for problems here adds the token o X 0 5 F Vi Vo a 0 25 to place r Finally the query transition 4 is enabled with o X a V 0 25 which is also the substitution for the successful query We need to extend the model in the following three ways in order to capture the fixpoint semantics 1 In the example above only one token was in place q after transition 2 fired but transition 3 needed this token two times to be enabled one for every arc q 3 Unlike the definition in section 2 3 tokens will not be removed in our model if a transition fires This reflects the fact that the tokens represent knowledge rather than resources that cannot be shared In other words our
3. If two transitions are enabled the one with the higher priority fires if it is not locked while the other has to wait If the two have the same priority they do both fire in parallel These priorities may change on certain events like a counter reaching zero an external condition becoming true time constraints etc The reader may refer to 3 for more ideas This seems to me the most promising approach for control specification although dynamically changing priorities may lead to confusion about what state the net is currently in 5 2 GAPCAD as a knowledge acquisition tool KADS Knowledge Acquisition and Design Structuring 22 is a methodology for developing knowledge based systems KBS Its emphasis lies on defining a language for semi formal specification of KBS Neither any knowledge elicitation technique nor implementational details are covered KADS offers some abstract templates called models which need to be filled during the specification phase A central model is the model of expertise which describes the contents of the knowledge base of the KBS in essentially three parts called layers 1 Inference Layer specifying the data flow 2 Task Layer specifying the control flow and 3 Domain Layer specifying the kinds of data The KADS methodology is widely used for new developments in the field of knowledge based systems Many knowledge acquisition tools are based on the KADS methodology It would be interesting to examine ho
4. 3 Ce mhentance DAEDALUS Figure 3 The GAPCAD architecture GAPCAD is a graphical user interface to DAEDALUS Therefore the system can be divided in three parts as illustrated in figure 3 1 DAEDALUS 9 provides generic object data classes and lattice classes and concepts like predicates literals substitutions etc GAPCAD uses heavily DAEDALUS code for those basic GAP functions like unifying computing the least upper bound and so on 2 The graph editor provides a front end for entering Petri nets GraphEd 5 was chosen because 4 GAPCAD ARCHITECTURE 19 it is generic in the sense that it provides application interfaces for adding domain specific functionality e it is easy to use e it is public domain Unfortunately some code had to be added in the core of GraphEd to provide an even easier entering of Petri nets for example using the left and right mouse buttons to create places and transitions or suppressing attempts to connect two places It was also important to ensure consistency between the GraphEd and the GAPCAD data structures for example token windows need to be deleted as soon as the corresponding place is deleted 3 The GAPCAD core itself has its own data structure While running the bottom up procedure it needs to be consistent with the GraphEd data structure for example to highlight a transition as well as the DAEDALUS data structure for example to use the routines for unifying Figure 4 show
5. 3 b 0 6 c 0 7 d 0 0 7a 0 3 b 0 4 ne 0 7 nd 0 0 4 a 0 3 b 0 6 c 0 7 d 0 0 Fixpoint reached The well founded model is Sp f5 U Sp 14 Sp 13 U Sp J3 This model is different to the one in example 1 not partial Note that the fixpoint was reached because step 4 results in the same sets as step 3 leading to a total model Due to the alternating fixpoint definition step 5 needs also be computed because Ap evaluates two Sp steps at a time 2 3 Coloured Petri nets A coloured Petri net is a triple N P T A consisting of disjoint sets P places and T transitions and a multiset A arcs over P x T U T x P forming a bipartite graph Each place p P is assigned a colourset C p and a multiset M p of tokens each of colour C p Coloursets can be viewed as data types and tokens are instances having a specific colour Each arc a p t A or t p A is attached a label L a of type C p Note that tokens as well as labels may contain variables of suitable type A marking is the distribution of tokens over all places of the net Each transition t T is assigned a Boolean guard G t expressing constraints on the variables binded to t For an extended and more formal definition of coloured Petri nets the reader may refer to 6 Let IN t p t A p E P OUT t t p EA p EP et p p t A and te p t p E A denote the vicinity of t 7 A transition t is called en
6. Petri net model caches all facts necessary for answering a query which could lead to a large number of tokens to be kept within the net Such an extension avoids conflicts between transitions which need the same token to be enabled as encountered in the example 2 The model presented so far only works with linear annotation lattices Consider the following example using the non linear lattice FOUR 3 AN EXTENDED PETRENET MODEL 11 Example 4 1 buy yen t 2 buy yen f 3 buy yen T yen t yen V if ee ent 2 After the firings of 1 and 2 buy contains the tokens yen t and yen f There are two possible substitutions for V V t and V f None of them satisfies the guard V gt T hence transition 3 is not enabled This is a contradiction to the fixpoint semantics of GAPs because L t f T In the example a token yen T should be in M p although none of the incoming transitions 1 and 2 delivered it We call such derived tokens reductants 7 Definition 3 1 Reductants Given a set M 01 H1 On Hn of tokens and a unification o with o 01 a o the token o 01 U u1 Hn is called a reductant The function reductants M computes the set of reductants derived from all subsets of M for which is defined For example a 6 T is a reductant of the set X b t a Y f It is important that every annotation in M is a c annotation to ensure that the least upper
7. Proceedings of ACM Symposium on Principles of Database Systems 1986 pp 1 15 D Debertin Parallizing inference in distributed knowledge based systems Master s thesis Institute of Algorithms and Cognitive Systems University of Karlsruhe in German F Gebhardt E Gro H Vo Concurrency constraints as control specifications for the MoMo language FABEL Report No 21 GMD Sankt Augustin 1994 H J Genrich Predicate Transition nets LNCS 254 Springer Verlag 1987 pp 207 247 M Hemsoldt GraphEd User Manual and Sgraph 3 1 Programmers Manual Included in GraphEd distribution available at ftp uni passau de in pub local graphed Kurt Jensen Coloured Petri Nets A High Level Language for System Design and Analysis in G Rozenberg Ed Advances in Petri Nets 1990 pp 342 416 Michael Kifer V S Subrahmanian Theory of Generalized Annotated Logic Journal of Logic Programming 12 1992 pp 335 367 D B Kemp P J Stuckey D Scrivastava Magic Sets and the Bottom up Evalua tion of the Well founded Model Logic Programming Proceedings 1991 International Symposium San Diego pp 337 351 Peter Kullmann SLG Resolution for Generalized Annotated Logic Master s thesis Institute for Algorithms and Cognitive Systems University of Karlsruhe 1995 in German Jim Lu Anil Nerode V S Subrahmanian Towards a Theory of Hybrid Knowledge Bases To appear in IEEE Transactions on Knowledge and Data Engineering Frank Maurer Hyp
8. well founded model is Sp 14 U Sp 13 wins c awins d restricted to the wins predicates 2 2 2 Annotated logic and the well founded model The semantics of the non monotonic negation in annotated logic is defined as follows Definition 2 9 Satisfiability of negated atoms Let J be an interpretation u T a c annotation and A a ground atom IE not A pw iff 1 A Zu The well founded semantics can be generalized to annotated programs Since the semantics of the satisfiability relation changed in annotated logic a partial model can have a different form Consider the following program with the lattice 0 1 p 0 7 not p 0 5 p 0 3 2 PREREQUISITES 8 The partial well founded model evaluates to p 0 3 not p 0 7 i e p u is true for all u lt 0 3 false for all u gt 0 7 and unknown for all 0 3 lt u lt 0 7 where a gt bif a b Example 2 reviews example 1 with annotated atoms In the table again only the wins atoms are presented They are abbreviated in a straightforward manner e g not wins a 0 3 is represented as 7a 0 3 Example 2 wins X W move X Y W Anot wins Y 0 5 move a b 0 3 move b a 0 4 move b c 0 6 move c d 0 7 Step t Sp hr Sp h y 0 a 0 0 6 0 0 0 0 d 0 0 na 0 0 b 0 0 ac 0 0 ad 0 0 1 a 0 3 6 0 6 c 0 7 d 0 0 a 0 3 b 0 6 c 0 7 ad 0 0 2 a 0 0 b 0 4 c 0 7 d 0 0 a 0 0 b 0 4 ne 0 7 nd 0 0 3 a 0
9. Implementation of an executable graphical representation of GAPs based on Petri nets Sebastian Jekutsch Project work report Institute for Algorithms and Cognitive Systems University Karlsruhe Contents 1 Introduction 2 Prerequisites 2 1 Generalized Annotated Programs 0 02 00 2 0004 2 2 Well founded semantics 2 2 1 Alternating fixpoint 2 2 2 Annotated logic and the well founded model 2 3 Coloured Petri nets 0 3 An extended Petri net Model 3 1 Negation freeGAPs 3 1 1 Algorithms for the extended Petri net model 3 2 Normal GAPs 0 0 4 GAPCAD Architecture 5 Further issues 5 1 Control flow specification 5 2 GAPCAD as a knowledge acquisition tool 6 Conclusion oN DW oO WwW W Ke 12 15 17 20 20 22 23 1 INTRODUCTION 3 1 Introduction The contents of this work is the implementation of the bottom up evaluation procedure of Generalized Annotated Programs GAPs A related procedure was presented in 2 Chap ter 3 3 and 13 The procedure has been formulated in terms of Coloured Petri nets 6 Also the extension to GAP clauses with negated body literals has been examined The developed tool called GAPCAD Generalized Annotated Program Construction And De bugging allows the interactive graphical entering of the Petri net representation of GAPs and therefore serves as an fron
10. M p u o L a M p M p U reductants M p M p M p subsumption M p See 9 for algorithms implementing reductants and subsumption The algorithms are based on the rather descriptive than procedural algorithms in 2 which need two minor corrections Firstly in 2 the initial marking is empty This leads to incompleteness because even without any fact the bottom element P NV of any predicate p is derivable Secondly the testing for fireability on page 19 needs to be modified in step 2 in the following way 2 Compute for all i 1 lt i lt n sets M ai u 0E uE of tokens of the place P e P k and a substitution o for every set M such that the following conditions hold a wiser th b ci lt a Hn c a if l oO are compatible in pairs d i if are compatible in pairs e There is no gt which satisfies a d The main procedure checks in each step for an arbitrary transition t whether any of its input places p et contains new tokens relative to the last step If not it checks another transition and stops if no transition satisfies this condition because this means that no new useful token was produced in the last step therefore the fixpoint is reached If on the other hand a transition is found it is fired if it is enabled Then the next step is taken There is an indeterminism in choosing an arbitrary transition in the beginning of each
11. P7 e Fire every transition in 7 e Delete all tokens out of places in Pt and restore the initial marking in these places This performs Sp 3 Redo these two steps This results in Sp Sp 4 If the outer fixpoint is not reached go to step 1 To test this the marking needs to be saved to compare it to the new marking after step 1 5 The fixpoint is reached Take step 1 one more time The resulting marking represents the well founded model The following table demonstrates the algorithm referring to example 5 Step Marking 0 0 not_p X 1 0 Initialisation 0 3 not_p X 1 0 1 fires X 0 0 not_p a 0 3 c fires a 0 7 not_p a 0 3 1 2 fire SRLS 0 3 not_p X 1 0 The same four steps repeated X 0 0 not_p a 0 3 a 0 7 not_p a 0 3 X 0 0 not_p a 0 7 Fixpoint reached a 0 3 not_p a 0 7 Well founded model R B S p X a X 0 0 not_p a 0 7 No fixpoint a PNrPNMNFNFNEH RS P This procedure has some problems Tokens need to be deleted explicitly and two different firing semantics need to be observed Also transitions are locked and unlocked periodically After all this results in something very different from Petri nets To check whether the fixpoint was reached many tokens need to be remembered and compared To implement this it will be best to divide every place from P in two parts one storing S the other 5 The solution in 8 bares the same disa
12. able 9 If F is not a closed formula then J H F iff I amp V F where V F denotes the universal closure of F There are two different kinds of negation in GAP the so called epistemic or explicit negation and the non monotonic not 7 requires symmetry between true and false e g a A t A fin FOUR The topic of non monotonic negation will be discussed in section 2 2 For GAPs without non monotonic negation the fixpoint operator has the following form Definition 2 5 Fixpoint operator Let P be a generalized annotated logic program GAP I a GAP interpretation and 7 a complete lattice Then a fixpoint operator Rp for bottom up computation of GAPs is defined as follows Rp J p U p p p pr H1 Pn Hn is a strict ground instance of a clause in P and T py p1 Pn Hn Rp may reach the least fixpoint lfp if for all strict ground instances A lfp Rp A is reached after a finite number of iterations This condition called fixpoint reachability property 7 holds for many GAP knowledge bases If the clause bodies of a program contain only variable v or only constant c annotations or if only finite or decreasing monotone functions appear in the program For instance if the knowledge base consists of Rains Monday 0 5 and Rains Monday 0 8 the least upper bound computed by the fixpoint operator would be Rains Monday 0 8 U 0 5 0 8 2 2 Well founded semantics For simplicity we define the well fou
13. abled iff the following conditions hold e For each incoming arc a p t E IN t there is at least one variable substitution o such that a token s M p exists with o s o L a This particular token s must not serve again as a resource for another substitution g for 7 i Recall that M p is a multiset therefore more than one token of this kind may be present 3 AN EXTENDED PETRENET MODEL 9 e All substitutions o 1 lt i lt N t are compatible o and g are compatible if their concatenation o o is defined In other words there is no assignment of two different values to the same variable e G t evaluates to true under o o102 om In this case o is called an enabling substitution There could be more than one enabling substitution under the same marking A transition could fire if it is enabled under a substitution o If a transition t fires the tokens M of the places are updated to M as follows Mi p o L p t if p et te Maal r Mp VoL tp ifpete et i Mi p o L p t U o LU t p if p at te M p otherwise Given a marking Mo a sequence t is called a firing sequence if for each i 1 lt i lt n it holds that t T is enabled under the marking M _ and t s firing results in the marking M The firing sequence changes the marking Mo into Mp 3 An extended Petri net Model 3 1 Negation free GAPs A GAP knowledge base is transformed into an exten
14. al i 5 keg lt violation a Figure 5 A top level inference structure the inference structure leads to more special and finally to atomic inference steps In Figure 6 a more detailed description of the propose knowledge source from Figure 5 is shown Coloured Petri nets on which the extended Petri net model is based can also be defined as parameter lt _ ca ca lt eer ae extensions Figure 6 Refinement of inference step propose hierarchical nets 6 It would be interesting to investigate the possibility of a graphically and semantically unified top down construction of knowledge bases beginning at the top knowledge level with the inference structure similar to Figure 5 applicating some local refinements as in Figure 6 and ending up with an extended Petri net as a representation for GAPs symbol level which can be debugged using GAPCAD and efficiently executed by DAEDALUS Some related issues need to be addressed e Are atomic inference steps really clauses e Where do the arc labels fit in What is their interpretation on the knowledge level e How can nets with non atomic transitions be executed 11 6 Conclusion This report described the theory and the implementation of an executable graphical repre sentation of generalized annotated programs using the notation and semantic of Petri nets The following topics were addressed the first time 6 CONCLUSION 24 The formalism presented here is bas
15. be a set of negative literals of atoms known to be false and P Hp UJ We define Sp 1 T37 0 where TA is the least fixpoint of Tp which was already defined above Sp J is the set of positive facts that are derivable An interpretation or model J is seen as the set of all literals that are true in J i e p HpU Hp I H p 2 PREREQUISITES 7 from P and Let Sp f Hp Sp The iteration steps Tay Sp 1 alter nate between subsets underestimation of the positive portion of the partial well founded model and supersets overestimation of the undefined and negative portion The alterna tion converges Let Ap I Sp Sp J1 then Ap is monotone therefore A AY exists Finally Sp A UA is the well founded model of P The reader may refer to 20 for a deeper treatment Consider as an example for the alternating fixpoint computation of the well founded model the following program taken from 20 It describes a game where one wins if the opponent has no moves left Example 1 move X Y A not wins Y The table shows the sets Sp and Sp at consecutive stages of the computation They are restricted to the atoms of the wins predicate since the move facts do not change during computation Step t Sp t Sp Ti lia 0 o awins a nwins b awins c nwins d 1 wins c wins b wins a awins d 2 wins c awins a awins b awins d 3 wins c wins b wins a Fixpoint reached Finally the
16. bound U is defined For markings M p this is always the case according to the next theorem A proof has appeared in 2 Theorem 1 Possible tokens of a place Let P be a GAP and N its transforma tion At all places p P of N T P A there are only tokens 0 u M p with u ET if P is finite 3 It is also possible to delete tokens from a place For example every time a 0 5 M p serves as a token for an enabling substitution of transition t with p t A a 0 6 will as well but not vice versa We say that a 0 6 subsumes a 0 5 because 0 6 gt 0 5 in the lattice 0 1 a 0 5 might be deleted from M p without changing the behaviour of the extended Petri net Definition 3 2 Subsumption Given two tokens 01 u1 02 42 E M the first subsumes the second if fy u2 and there exists a substitution o such that 02 o 01 The function subsumption M computes all tokens in M which are subsumed by at least one other token in M For example a t and a f are both subsumed by their reductant a T whereas subsumption X 8 t a f a 8 T is empty Different from the definition provided here in 7 derived rules are named reductants Note that tokens are representations for annotated atoms due to the presented transformation 3 AN EXTENDED PETRENET MODEL 12 To summarize the three extensions presented above we redefine the update M 4 of the marking M due to the firing of transiti
17. ded Petri net N P T A according to the subsequent rules suppose the clauses are enumerated from 1 to n e Each predicate p is a place p P in the net e Each clause c 1 lt lt n is a transition c T in the net e Let O be the type of the object part and 7 the annotational lattice of predicate p Then C p Ox T e For every clause c of the form poloo fo p 01 H1 A A Dm Om Hm and 1 lt i lt m the net contains the arcs a p c with the labels L a 0i 4 where pi is a new variable annotation If u is a c annotation then u lt fj is added as a conjunctional condition to the guard of transition c In addition the net contains the arc ao c po with the label L ao 00 fio where Lo if uo is c annotation flo 4 M ilu is the same variable as po if Ho is v annotation f Pi Pr if wo f P1 Pn The p1 fn are defined recursively in the same way Note that N a a for every a T andn n7 3 AN EXTENDED PETRENET MODEL 10 e The initial marking is Vp P Mo p X n7 where X is a new variable for all p and X NT C p Queries can be added to the net as they are headless clauses The following abstract example illustrates the transformation in its details Places are drawn as circles and transi tions as rectangles Typing information is omitted and C p C q C r a x 0 1 All uppercase letters are variables Example 3 1 pla
18. dvantages An alternative solution is described in 16 This is more closely to Petri nets but adds inhibitor arcs and requires the explicit computation of the greatest deadlock of the net to obtain the unfounded set of a program A non empty subset S C P of places in a Petri net is called a deadlock if every transition having an output place in S has an input place in S Note that in this approach enabling tokens will be removed if a transition fires according to the definition of the update of markings in ordinary Petri nets The greatest disadvantage 4 GAPCAD ARCHITECTURE 17 of the approach in 16 is the translation schema Every place represents a ground atom rather than a predicate which makes it of little use for graphical applications addressed in this report To summarize there is no known elegant method for Petri net computation of the well founded model of normal programs In the next section a tool implementing the routines in section 3 1 is presented It does not allow normal programs and therefore does not implement the well founded semantics due to the problems encountered above 4 GAPCAD Architecture GAPCAD is the implementation of the procedures presented in section 3 1 This chapter briefly reviews the concepts behind GAPCAD 7 ee ett ht tel tld a g edited Editi unconstrained 1 pe Botoi simulation Status lteratiry f Halt Step j i Ge Clear Ket Speed 53 a 1 Ceti f Puremty Joes
19. ed on Coloured Petri nets which provide a natural way to express constraints on the annotations using the concept of transition guards In 2 and 13 predicate transition nets 4 were used An execution model for the Petri net based computation of the well founded model of normal programs was presented Another alternative is described in 16 which is based on classical logic rather than on annotated logic Finally the GAPCAD implementation provides an interesting graphical user interface for entering GAPs and serves as an basis for a more sophisticated tool Promising ideas in this direction were also presented in this report Three possible future research direction are e Development of a better Petri net based realisation of the well founded semantics e Provision of more support for entering GAPs for DAEDALUS especially for the sorts of the predicates e Viewing GAPCAD in a more general frame for support of knowledge acquisition along the lines of 21 and 22 Acknowledgements I d like to thank Joachim for supervising and supporting this work Michael Himsoldt for providing GraphEd and especially Peter for many quick respond ings to my never ending wishes remarks and misunderstandings concerning DAEDALUS REFERENCES 25 References 1 2 2 10 11 12 13 14 15 16 Bancilhon F Maier D Sagiv Y Ullman D D Magic Sets and other strange ways to implement logic programs
20. ere is no clause in P whose head is p or there exists such a clause c and at least one of the following holds a some positive or negative subgoal of the body of c is false in I b some positive subgoal of the body of occurs in A The greatest unfounded set of P with respect to I denoted Up I is the union of all un founded sets of P w r t I In the example program P and interpretation I above Up is p b p a The well founded semantics uses Up I to draw negative conclusions The transformations Tp Wp are defined as follows e Tp L is the usual fixpoint operator i e p Tp L iff there is some instantiated clause c of P such that c has head p and each subgoal literal in the body of is true in interpretation J Tp J is called the inner fixpoint e Wp I Tp I U n Up I Wp is monotonic 19 Definition 2 8 Well founded model Let Jo 9 Ja41 Wp Ia and T Ua Lo I the least fixpoint of Wp also named outer fixpoint defines the well founded model of P The example program P has the well founded model q4 b p a nagla ap b which is not partial As an example for partial model consider the program which only contains the clause p a ap a The well founded model is empty therefore the truth value of p a is unknown 2 2 1 Alternating fixpoint In the following the alternating fixpoint characterisation of the well founded model is pre sented shortly according to 20 Let I
21. ermedia based Knowledge Engineering for Distributed Knowledge Based Systems Diss thesis in German infix Sankt Augustin 1993 P Meseguer A new method to checking rule bases for inconsistency a Petri Net approach Proceedings of ECAI Stockholm 1990 pp 437 442 Tadao Murata V S Subrahmanian Toshiro Wakayama A Petri Net Model for Rea soning in the Presence of Inconsistency IEEE Transactions on Knowledge and Data Engineering Vol3 No 3 September 1991 pp 281 292 Allen Newell The Knowledge Level Artificial Intelligence 18 1982 pp 82 127 A Th Schreiber P Terpstra P Magni M van Velzen Analysing and Implementing VT Using CommonKADS KADS Workshop T Shimura J Lobo Tadao Murata An Extended Petri Net Model for Normal Logic Programs IEEE Transactions on Knowledge and Data Engineering Vol 7 No 1 Feb 1995 REFERENCES 26 17 V S Subrahmanian Amalgamating Knowledge Bases ACM Transactions on Database Systems 19 2 1994 pp 291 331 18 V S Subrahmanian S Adali A Brink R Emery Jim Lu Adil Rajput T J Rogers R Ross C Ward HERMES Heterogeneous Reasoning and Mediator System Draft University of Maryland 1995 Available via WWW 19 A van Gelder K Ross and J Schlipf The Well founded Semantics for General Logic Programs Journal of the ACM Vol 38 No 3 July 1991 pp 620 650 20 A van Gelder The Alternating Fixpoint of Logic Programs with Negation Extended Abstract Proc 8th Sympos
22. fying the control flow has two advantages 1 Efficiency Even if a transition is enabled its firing does not necessarily enlarge the fixpoint set If a query has been stated the point becomes obvious Consider as an example the following program PX GX qla q b 5 FURTHER ISSUES 21 qlc Query pla The query is answered in two steps but a pure bottom up procedure computes the whole model A possible way to resolve this overhead is the magic set approach 1 where the clause x would be rewritten to p a q a depending on the known query 2 Side effects Consider the case where the firing of a transition causes a side effect output to the screen In the most cases the user is only interested in the final solution not in several in between results so this transition should fire as late as possible This can only be achieved if the control flow is explicitly specified Of course this argument is not a theoretical but a practical one There are at least three possibilities to describe the control flow Firm strategy Production systems which also work in a bottom up manner usually re solve the conflict that arises if more then one rule at the time is ready to fire via some heuristics like Take the most recent enabled rule or Take the rule with the largest number of premises or so In GAPCAD a rather simple conflict resolution is imple mented It iterates through the set of transitions If the curre
23. hould be easy because of the simple class structure Unfortunately GraphEd provides no graph overview facility For large GAPs the graph becomes too complicated Also the automated graph drawing of a loaded GAP is far from optimal For more easy entering of graphs it would be useful to implement hierarchical coloured Petri nets 6 5 Further issues In this chapter two further subjects are addressed 1 control flow specification and 2 GAPCAD as a knowledge acquisition tool 5 1 Control flow specification From a software engineering point of view the extended Petri net model specifies the data flow The places are data containers and the transitions represent the operations on the data especially if the guards contain more complex functions On the other side no control flow specification is given Each enabled transition may but need not fire which causes indeterminism This is sound according to the fixpoint semantics 2 A specification of the control flow i e the determination which of the enabled transition fire in any state of the net is not necessary It could even make the extended Petri net model incomplete if it never allows a particular transition to fire which contribution to the fixpoint set is not empty This shows that a control flow specification needs to satisfy some conditions For example it needs to be fair i e every enabled transition fires sometime until the fixpoint is reached However explicitly speci
24. is an annotation then A u is an annotated atom An annotated atom containing no occurrence of object variables is ground A is called the object part and pn is called the annotation part of A u Definition 2 2 Annotated clause If A pis an annotated atom and B j4 By uk are c or v annotated atoms then A p By A A BE ue is an annotated clause A p is called the head of this clause whereas By py4 Bk Hk is called the body All variables object or annotation are implicitly universally quantified Any set of annotated clauses is called a Generalized Annotated Program GAP Definition 2 3 Strictly ground instance Suppose that C is an annotated clause A strictly ground instance of C is any ground instance of C that contains only c annotations Let H be the Herbrand base of the program An annotated logic interpretation J is a mapping H T from the base onto a lattice Definition 2 4 Satisfiability Let I be an interpretation u T a c annotation F and Fy formulae and A a ground atom 1 ITH At pir iA ey 2 TE AA p iff a t X KA 3 IEF FAR if IE Fi and I H Fo 4 TE F v F iff T F or Ti F 5 IH F Rif IE RA orl F 2 PREREQUISITES 5 6 LE Fo Fo iff hE FP Fy and IE Fy Fj 7 I Va F iff I amp a t F for all ground terms t where x is an object or annotation variable 8 I sr F iff I a t F for some ground term t where g is an object or annotation vari
25. itions are required Definition 3 3 Unifier mgua of tokens Tokens s 0 u as well as arc labels con sist of two parts its first being the object part s o and its second being the annotation part s u Let mgu o1 02 denote the usual most general unifier of o and 02 Given two tokens labels 51 52 the most general annotational unifier denoted mgua s1 s2 is defined as follows magus 887 U sgn sann if 54 is v annotation yi obs mgu s s3 if s and s are c annotations and sf gt sg unde fined otherwise mgua s1 s2 If mgu so 89 is not defined mgua s1 52 is not defined either Note that mgua is not symmetric If mgwa s1 s2 is defined then s and sz are said to be unifiable 3 AN EXTENDED PETRENET MODEL 13 ror example Mgual X a 0 5 b Y 0 4 X b Y a and mgual a t a f is not Definition 3 4 Compatibility of annotation substitutions Two substitutions V a and V b which assign different c annotations a and b to the same annotation variable V are compatible if a and b are comparable due to the ordering of the underling lattice In this case their concatenation V a V b is defined as V N a b0 This definition is easily extended to cases with more than two substitutions Definition 3 5 Concatenation of mguas The substitutions in mguas may be divided in object variable substitutions and annotation variable substitutions The concatenati
26. ium on Principles of Database Systems March 29 31 Philadelphia 1989 21 J Walther et al MoMo GMD Sankt Augustin 1993 Germany Available via WWW 22 B J Wielinga A T Schreiber J A Breuker KADS A Modelling Approach to Knowl edge Engineering Knowledge Acquisition 4 5 53 1992 23 D Zhang D Nguyen PREPARE A Tool for Knowledge Base Verification IEEE Transactions on Knowledge and Data Engineering December 1994 Vol 6 Number 6 pp 983 989
27. nded semantics for classical logic in the first case according to 19 Definition 2 6 Normal program A normal program is a set of clauses of the form A B1 A A Brn Anot Bni A A not Bm where A B1 Bm are atoms Let P be a normal program and Hp its Herbrand base consisting of all atoms that are grounded in every possible way using all predicates functions and constants that appear in P For a set of literals S the expression S denotes the set formed by taking the complement of each literal in S Consider as an example the following program P pla not q b qb A function f is finite if f s DOM f is finite and f is decreasing if for arbitrary arguments T1 En f ti n lt zi for al 1 lt i lt n 2 PREREQUISITES 6 P is anormal program with Hp p a p b g a q b and 4 p a agq a p a q b The well founded model of a normal program P is a partial model i e a set of literals which contains not necessarily all atoms of Hp Therefore it can be seen as a three valued model In the above example an interpretation T q b aq a states that q b is true in I and therefore aq 6 is false in T g a is false in J and the truth values of p a p b are unknown in J Definition 2 7 Greatest unfounded set Given a partial interpretation J and a nor mal program P A C Hp is called an unfounded set of P with respect to I if each atom p A satisfies the following condition Either th
28. new step This choice should be fair i e every transition is checked a finite count of steps after it has been checked last See also section 5 1 for a discussion of this point Main procedure Input Extended Petri net N P T A with initial marking Output N with marking which represents the fixpoint iterate through all t T if Jp et with new tokens since last firing of a transition then if t is enabled then fire t restart iteration 3 AN EXTENDED PETRENET MODEL 15 3 2 Normal GAPs This section describes a method how to handle non monotonic modes of negation based upon the well founded semantics in the extended Petri net formalism using a direct imple mentation of the alternating fixpoint computation The reader may also refer to 8 for a similar presentation not based on Petri nets The transformation of a normal GAP to an extended Petri net N P T A is per formed as follows Every negated atom of the form not p is treated as a new not negated atom not_p i e for every predicate a dual negative predicate is added to the vocabulary This transforms the normal GAP into a negation free GAP The set of places P is therefore divided into two sets Pt containing the positive literals and P7 containing the previ ously negative literals such that P Pt UP The transformation process is similar to the one described in section 3 1 but with the following differences e For every clause c of the form pol
29. nt transition t is enabled and some new token is in any of the places in e it fires and the iteration restarts This algorithm terminates because the fixpoint is reachable and its occurrence causes no new token being in any place There is one major disadvantage in completely specifying the control flow Two tran sitions being enabled at the same time express the possibility to fire them in parallel There is not always the need to completely sequentialize the order of firing In the case of Petri nets a control specification should be better viewed as a restriction of freedom rather than a total sequentialisation The next two techniques take this into account Petri nets We used the Petri net model to define the data flow although Petri nets usually specify the control flow It is possible to unify both applications Orthogonally to the control place control yflow data data data gt e data flow we embed the transitions in a second Petri net where the places contain control tokens A transition may be enabled only if its input control places contain tokens In 3 it is shown that as soon as the control flow gets more complex Petri nets 5 FURTHER ISSUES 22 tend to be difficult to survey so this kind of control flow specification appears to be not very natural Priorities In 3 it is suggested to express the control flow through dynamically given priorities between transitions or temporally locks of transitions
30. on O102 0On Of N MgUas C1 On is defined as the usual concatenation of the object vari able substitutions unioned with the above defined concatenation of the annotation variable substitutions The following algorithms do not use the notion of transition guards Instead they are specialized for the bottom up evaluation of annotated programs encoded in Petri nets The guards are implicitly checked in the mgua routine defined above Testing for fireability of a transition Input Extended Petri net N P T A Transition c T Output Maximal set of mguas each enabling c cis not enabled if the set is empty is a set of sets of possible substitutions for c for all arcs a IN c do Let a be p c A Pa Ga is the set of all possible substitutions according to a for all tokens s M p do if uni fiable s L a then Ya Ya U Mguals L a if Ya then return O OU pa Let be 1 pjo WV is a set of all enabling substitutions for c for all permutations o4 7 9 with o E y EO 1 lt i lt O do if o1 0 9 are compatible in pairs then Y Y U o102 a1 return Y Firing of a transition Input Extended Petri net N P T A Transition c T Set W of c enabling substitutions Output N with updated marking using every o V 3 AN EXTENDED PETRENET MODEL 14 for all arcs a OUT c do Let a be c p A for allo Y do M p
31. on t T 1 MP p Wi UEP there 2 Miet p Me p u reductants M p 3 Migi p MEST p subsumption Mif4 p With this extension example 4 works as expected Transitions 1 and 2 place the tokens yen t and yen f in p respectively M 4 p evaluates to yen t yen f yen T and M p to yen T which enables transition 3 since T gt T It is worth noting that our model captures the operational semantics of a GAP which means that if there is a GAP for which the least fixedpoint reachability property does not hold e g from p 0 p ite p 2 q 1 p 1 it is never possible to answer the query q 1 the corresponding Petri net cannot answer this query as well and runs forever The following theorems have been proven in 2 and capture the soundness and com pleteness of the proposed extended Petri net model with respect to the semantics of GAPs Theorem 2 Soundness Let P be a GAP with clauses c1 Cn Cn a query and N the extended Petri net defined on P If there is a successful firing sequence in N then C1 n 1 E Cn Theorem 3 Completeness Let P be a GAP with clauses c1 Cn Cn a query and N the extended Petri net defined on P If c1 Cn 1 H En then there is a successful firing sequence in N 3 1 1 Algorithms for the extended Petri net model Before presenting algorithms for the testing for fireability of a transition and updating of the net marking some more defin
32. oo fo p 01 H1 A A Pm Om Hm and 1 lt i lt m the net contains the arcs a p c with the labels L a 0 mi where ji is a new variable annotation In case that u is a c annotation If p PH then u lt m is added as a conjunctional condition to the guard of transition c otherwise if p P then pm gt ff is added to the guard In addition the net contains the arc ao c po with the label L ao 00 fio where fig is defined as in section 3 1 e The initial marking is Vp P t Mo p X N7 and Vp P Mo p X UT where X is a new variable for each p Additionally new transitions 7 will be introduced as shown in example 5 e Given two dual places p Pt and not_p P a transition c T is added to T with an empty guard The arcs p c and c not_p both with labels X V with new variables X and V are added to A If such a transition fires all tokens from p are moved to not_p Example 5 1 pla 0 3 2 pla 0 7 not_p a 0 5 A pla 0 2 en X V c a W 2 X V V lt 0 5 pg ci ee 3 AN EXTENDED PETRENET MODEL 16 The following algorithm schema describes how to compute the well founded model 1 Compute the fixpoint as described in section 3 1 without firing any transition from T This realizes Sp 2 Transfer all tokens along the transitions in 7 i e e Delete all tokens out of places in
33. s the relevant classes _ ISA gt HAS A with cardinality seeeceee gt Points to 1 Re OTe Se CD y ED Gi DAEDALUS GAPCAD Core GraphEd Figure 4 The GAPCAD class structure One goal was to separate the graph editor from the GAPCAD core as far as possible to make it easily possible to use another editor Two interfaces were defined gapcad2ui This contains procedures which GAPCAD provides for the editor such as creat ing and deleting nets places transitions arcs firing of transitions starting Daedalus bottom up evaluation loading saving printing the GAP etc ui2gapcad This specifies services which the editor needs to provide such as displaying new nodes and edges highlighting of a node setting labels or refreshing token windows Some extensions of GAPCAD would be useful 5 FURTHER ISSUES 20 Currently no parallelizing is supported Every enabled transition is immediately fired It would be interesting to compute the conflict set of transitions which are enabled see also chapter 5 1 It would be easy to implement this because there are two different procedures for checking for fireability and firing of a transition For a more efficient computation it would be useful to switch of the graphical repre sentation completely It could be interesting to examine the firing sequence as a list In 23 and 12 a Petri net based validation check of rule based programs is described Integration in GAPCAD s
34. sites 2 1 Generalized Annotated Programs In this section the generalized annotated logic introduced by M Kifer and coworkers 7 is sketched It provides an universal language for dealing with temporal uncertain and inconsistent information or in general with parametric data with provides the algebraic structure of a lattice For a comprehensive description of the language the reader may refer to 10 7 Salient features of the language are the so called annotations which are constants vari ables and terms over a complete lattice 71 Figure 1 presents some examples for complete lattices The following definitions are from 7 Definition 2 1 An annotation is either an element of T c annotation an annotation variable v annotation or a complex annotation term t annotation Annotation terms are 1A complete lattice T lt is a partial ordering with respect to lt a least upper bound lub U and a greatest lower bound glb N for every subset of 7 A lattice is linear if lt is a total ordering 2 PREREQUISITES 4 4 ja gt b we kK Doa CS tap aes ff ye Sy t oe Si INA FOUR DEFAULT Figure 1 Some lattices used in this report defined recursively as follows Members of 7 and variable annotations are annotation terms In addition if j Hn are annotation terms then f u1 Hn is a complex annotation term If A is a usual atomic formula of datalog in 7 predicate calculus and yz
35. t end to DAEDALUS 9 GAPCAD also permits the mon itoring and step by step execution of GAPs In contrast to DAEDALUS which performs a query initiated backward chaining SLG resolution the forward chaining procedure in GAPCAD computes the whole model of the GAP based on the fixpoint semantics To compute normal GAPs i e clauses with negated literals in the body an algorithmical pro posal for the computation of the well founded model according to the alternating fixpoint characterisation 20 is presented This will ensure answer compatibility to DAEDALUS The implementation uses DAEDALUS routines a generic graph editor 5 and in between code for representing the Petri net and computing the fixpoint It was taken care to define a useful interface between the GAPCAD core and the graph editor for possibly exchange with a different editor The outline of this report is as follows Firstly the generalized annotated logic the well founded semantics and the Coloured Petri net formalisms are described shortly Next the extended Petri net model is presented in the first instance without negated literals and subsequently including them Chapter 4 addresses the architecture of GAPCAD and the final chapter discusses some further issues and an outlook This text does not cover GAPCADs actual purpose To serve as a front end for developing mediatory knowledge bases for the integration of heterogeneous and inconsistent information sources 2 Prerequi
36. w well GAPCAD meets the requirements of KADS tools since e annotated programs form a logic programming language which are widely used as prototyping languages for the development of KBS e the institute is looking for tools which aid in developing mediatory knowledge bases e the Petri net model is very similar to the description of the inference layer in KADS This point is discussed in the sequel The inference layer of the model of expertise in KADS contains a description of the data flow in the KBS to be developed Its graphical representation called inference structure contains meta classes squares the data and knowledge sources or inference steps circles the operations on the data See Figure 5 as an example for an inference structure It shows the data flow in a generic configuration task 15 Notice the similarity to Petri nets meta classes are places and knowledge sources are transitions but one should notice the dual graphical syntax circles are squares and vice versa The semantics of the inference structure is not formally specified in KADS The syntactical equivalence between the two was used in MoMo 21 However as our extended Petri net model represents specific program clauses on the symbol level the inference structure in KADS describes only the very idea how the expert performs the configuration task on the knowledge level 14 Further refinement of 6 CONCLUSION 23 Eag eo Eag 2 eo eal aL e
Download Pdf Manuals
Related Search