# Situated nonmonotonic temporal reasoning with BABY-SIT

发布时间:2021-11-29 06:15:45

93

Situated nonmonotonic temporal reasoning with BABY-SIT

Erkan T?n and Varol Akman?

Department of Computer Engineering and Information Science, Bilkent University, Bilkent, Ankara 06533, Turkey E-mail: {tin,akman}@cs.bilkent.edu.tr

After a review of situation theory and previous attempts at ‘computational’ situation theory, we present a new programming environment, BABY-SIT, which is based on situation theory. We then demonstrate how problems requiring formal temporal reasoning can be solved in this framework. Speci?cally, the Yale Shooting Problem, which is commonly regarded as a canonical problem for nonmonotonic temporal reasoning, is implemented in BABY-SIT using Yoav Shoham’s causal theories.

reasoning [19]. There are numerous works in AI to that effect. Neither do we want our work to be understood as a temporal data (world model) manager. Regarding this issue, cf. [20] for a system which is in fairly wide use, and seems to be popular due to its speed.

2. Basic situation theory Situation theory is a uni?ed mathematical theory of information content. The original proposal was due to Jon Barwise and John Perry [3]. The theory has matured over the last decade or so [10] and various versions of it have been applied to a number of problems in logic, language, and cognition [6]. In this section, we introduce the basic notions of situation theory. To this end, we follow the de?nitions given by Devlin [7] almost verbatim. We also use his notation. The basic ontology of situation theory consists of entities that a ?nite cognitive agent individuates and/or discriminates as it makes its way in the world. These entities are known as uniformities and include: – Individuals: objects that the agent individuates as single, essentially unitary items; denoted by a, b, c, etc. – Relations: uniformities that hold of, or link together speci?c numbers of, certain other uniformities; denoted by P , Q, R, etc. – Spatial locations: these are not necessarily like the ‘points’ of mathematical spaces, for they can have a spatial extension; denoted by l, l , l0 , etc. – Temporal locations: as with spatial locations, temporal locations may be either points in time or regions of time; denoted by t, t , t0 , etc. – Situations: structured parts (concrete or abstract) of the world individuated by the agent; denoted by s, s , s0 , etc. – Types: higher order uniformities; denoted by S, T , U , etc.

1. Introduction Serious thinking about the computational aspects of situation theory has started only a decade ago [13]. There have been recent proposals in this direction (i.e., PROSIT and ASTL), with varying degrees of divergence from the ontology of the theory. We believe that a programming environment incorporating bona ?de situation-theoretic constructs will be useful in AI and describe our very recent BABY-SIT implementation. A brief account of PROSIT and ASTL is also offered in order to put BABY-SIT into perspective. While BABY-SIT is a general-purpose programming environment, in this paper we demonstrate its operation on a well-known example from the AI literature, viz. the Yale Shooting Problem (YSP). Since our essential aim is to display the available functionalities of BABY-SIT for representational issues in AI, we simply borrow a theoretical approach – causal theories due to Yoav Shoham – to solve the YSP [17,18]. It should be noted that our goal in writing this paper is not to offer a new approach to formal temporal

? To

whom correspondence should be addressed.

AI Communications 10 (1997) 93–109 ISSN 0921-7126 / $8.00 ? 1997, IOS Press

94

E. T?n and V. Akman / Situated nonmonotonic temporal reasoning with BABY-SIT

A scheme of individuation, i.e., a way of carving the world into uniformities, is an essential aspect of situation theory. This is the agent-relative framework that ‘picks out’ the ontology. In other words, the basic constituents of the theory are determined by the agent’s scheme of individuation. In situation theory, information is always taken to be information about some situation and is in the form of discrete items. Infons are these discrete items of information and situations are ?rst-class objects which describe limited portions of the real world. Infons are denoted as R, a1 , . . . , an , i , where R is an nplace relation, a1 , . . . , an are objects appropriate for the respective argument places of R, and i is the polarity assigned to the sequence R, a1 , . . . , an . A polarity value of 1 (respectively, 0) indicates that objects a1 , . . . , an do (respectively, do not) stand in the relation R. If R is an n-place relation and a1 , . . . , am , m n, are objects that are appropriate for the argument places i1 , . . . , im of R, and if the ?lling of these argument places is suf?cient to satisfy the minimality conditions for R, then for i ∈ {0, 1}, R, a1 , . . . , am , i is a well-de?ned infon. Minimality conditions for R are the collection of conditions that determine which particular groups of argument roles need to be ?lled in order to produce an infon. If m < n, the infon is said to be unsaturated; if m = n, it is saturated. Given an infon σ and a situation s, we write s |= σ to indicate that infon σ is ‘made factual’ by s – or that σ is an item of information that is true of s. It is also said that s supports σ. In case σ is not true of s, this is denoted by s |= σ. Situations are intensional objects. For this reason, abstract situations are proposed to be their counterparts amenable to mathematical manipulation. Given a real situation s, the set {σ | s |= σ} is the corresponding abstract situation. Situations in which a sequence is assigned both polarities are incoherent. For instance, s is incoherent if s |= has, alice, A?, 0 and s |= has, alice, A?, 1 . This is a situation in which Alice holds the A? and she does not hold the A? in a particular card game. There cannot be a real situation s validating this. Nevertheless, the sequence has, alice, A? may be assigned both polarity values for spatio-temporally distinct situations (say, two subsequent card games s and s ). Situation theory provides a collection of basic types that can be used for individuating or discriminating uniformities in the real world. The higher types of the theory are de?ned by (recursively) applying type-

abstraction procedures over the basic types [7]. There are nine basic types: 1. 2. 3. 4. 5. 6. 7. 8. 9. T IM : the type of a temporal location. LOC: the type of a spatial location. IN D: the type of an individual. RELn : the type of an n-place relation. SIT : the type of a situation. IN F : the type of an infon. P AR: the type of a parameter. P OL: the type of a polarity. T Y P : the type of a type.

For each basic type T other than P AR, there is an in?nite collection T1 , T2 , . . . of basic parameters, denoting arbitrary objects of type T . Occasionally, a, ˙ s, t, l, etc. are used to denote parameters for objects ˙ ˙ ˙ of type IN D, SIT , T IM , LOC, etc., respectively. Given an object x and a type T , we write x : T to indicate that x is of type T . Abstraction can be captured by allowing parameters in infons. Parameters are generalizations over classes of non-parametric objects (e.g., individuals, spatial locations). For example, sees, x, alice, 1 ˙ and sees, x, y, 1 are parametric infons where x ˙ ˙ ˙ and y stand for individuals. The former says that ˙ someone sees Alice, whereas the latter says that someone sees someone else. A situation s is said to be a part of another situation s – or s is a subsituation of s – just in case ?σ[s |= σ → s |= σ]. The part-of relation (denoted by s ? s) is re?exive, anti-symmetric, and transitive, and consequently provides a partial ordering of the situations. In situation theory, information ?ow [8] is made possible by a network of abstract links between situation types. These links are called constraints. They capture systematic regularities connecting situations of one kind with situations of another. One way to picture the functioning of constraints is to think of a constraint S ? T as providing a passage that leads from the class of all situations of type S to the class of all situations of type T . Given a situation s : S, the constraint S ? T provides the information that there is a situation t : T . Hence, if an agent attuned to this constraint encounters a situation s and recognizes that s is of type S, then it has the information that the world of which s is a part is such that there is a situation t of type T . The role of constraints in information ?ow is best illustrated with an example. The statement Smoke means ?re expresses the law-like relation that links

E. T?n and V. Akman / Situated nonmonotonic temporal reasoning with BABY-SIT

95

situations where there is smoke to situations where there is a ?re. If Tsmoke is the type of situations where there is smoke and Tf ire is the type of situations where there is a ?re, then by being attuned to the constraint Tsmoke ? Tf ire , an agent can pick up the information that there is a ?re in a particular situation by observing that there is smoke (in that particular situation).

3. Situation-theoretic computational systems Two pioneering systems, PROSIT and ASTL, that we will review in this section incorporate only some of the original features of situation theory; the remaining features they omit for the sake of achieving particular goals. In BABY-SIT, which we review in the next section, we have tried to stick to the essentials of the theory and adopted the ontology which was ?rst put forward by Barwise and Perry [3], and then re?ned by Devlin [7]. 3.1. PROSIT PROSIT (PROgramming in SItuation Theory) was developed by Nakashima et al. [15,16] and implemented in Lisp. In PROSIT one can de?ne situations and assert knowledge into particular situations. It is also possible to de?ne relations between situations in the form of constraints. There is an inference engine similar to a Prolog interpreter. One can assert facts that a situation will support. For example, if situation s1 supports the fact that Bob is a young person, this can be de?ned in the current situation s as: s: (!= s1 (young Bob)) PROSIT has no special polarity argument in infons. Thus, (young Bob) represents a positive infon whereas (no (young Bob)) stands for the negation of that infon. In PROSIT, there exists a tree hierarchy, with the situation top (the global situation) at the root of the tree. One can traverse the tree using special predicates. It is possible to make queries from a situation about any other situation, the result depending on where the query is made. If a situation s2 is de?ned in the current situation, s1, then s1 is said to be the owner of s2. PROSIT has two relations de?ned between situations. These are the subtype relation and the subsituation relation. When the subtype relation, denoted by

(-> s1 s2), is asserted, it means that s1 supports every infon valid in s2 and that s1 ‘respects’ (to be de?ned shortly) every constraint that is respected by s2, i.e., s2 becomes a subtype of s1. The subsituation relation, denoted as (s< s1 s2), is the same as (-> s1 s2) except that only infons, but no constraints, are inherited. There is no notion of situation type in PROSIT. For this reason, one cannot represent abstractions over situations and specify relations between them without having to create situations and assert facts to them. Constraints can be speci?ed using either of the three relations ?, ?, and ?. Constraints speci?ed using ? (respectively, ?) are forward (respectively, backward) chaining constraints; the ones using ? are both backward and forward chaining constraints. Backward chaining constraints are of the form (? head fact1 . . . factn ). If all the facts are supported by the situation, then head is supported by the same situation. Forward chaining constraints are of the form (? fact tail1 . . . tailn ). If fact is asserted to the situation, then all the tail facts are asserted to the same situation. For a constraint to be applicable to a situation, the situation must be declared to ‘respect’ the constraint. For example, to state that every man is a human being, one writes (*X denotes a variable): s: (resp s1 (<= (human *X) (man *X))) This states that s1 respects the stated constraint (namely, every man is a human being). Since assertions are situated, a situation may or may not respect a constraint depending on where the query is made. If we assert: s: (!= s1 (man Bob)) then PROSIT will af?rmatively answer the query: s? (!= s1 (human Bob)) 3.2. ASTL Black’s ASTL (A Situation Theoretic Language) is another programming language based on situation theory [4]. One can de?ne in ASTL constraints and rules of inference over the situations. An interpreter, implemented in Lisp, processes ASTL de?nitions and answers queries. ASTL allows individuals, relations, situations, parameters, and variables. These constitute the basic terms of the language. Complex terms are in the form of i-terms (which are simply infons of the form rel, arg1 , . . . , argn , pol ), situation types, and situations. Sentences in ASTL are constructed from terms

96

E. T?n and V. Akman / Situated nonmonotonic temporal reasoning with BABY-SIT

and can be constraints, grammar rules, or word entries. A situation type is given as [par | cond1 . . . condn ], where condi has the form par |= i-term. For example, if situation S1 supports the fact that Bob is a young person, this can be written as (S is a parameter): S1: [S | S |= young,bob,1 ] The colon indicates that S1 supports the situation type on its right. The supports relation in ASTL is global rather than situated. Consequently, query answering is carried out independently of the situation in which the query is made. Constraints are actually backward chaining constraints. Each constraint is of the form sit0 : type0 ? sit1 : type1 , . . . , sitn : typen , where siti is a situation and typei is a situation type. If each siti , 1 i n, supports the corresponding situation type, typei , then according to the above constraint sit0 supports type0 . For example, the constraint that every man is a human being can be written as follows (*S and *X are variables): *S: [S | S |= human,*X,1 ] ? *S: [S | S |= man,*X,1 ] An interesting property of ASTL is that constraints are global. Thus, a new situation of the appropriate type need not have a constraint explicitly added to it. Assume that situation S1, supporting the fact that Bob is a man, is asserted: S1: [S | S |= man,bob,1 ] This together with the constraint above would give: S1: [S | S |= human,bob,1 ]

4. Fundamental notions of BABY-SIT

BABY-SIT has been developed in KEE (Knowledge Engineering Environment) [12]. The BABY-SIT desktop runs on a SPARCstation. The primary motivation underlying BABY-SIT is to facilitate the development and testing of programs in domains ranging from linguistics to AI within a uni?ed framework built upon situation-theoretic constructs [23,25]. BABY-SIT accommodates the basic features of situation theory and, compared to the existing approaches [4,5,16], enhances these features [24,26]. Devlin’s reformed approach to situation theory [7] has been extensively used in designing the formal skeleton of BABY-SIT. Akin to the basic types in situation theory, there are nine basic types which are employed in BABY-SIT: ?IND (individuals), ?TIM (times), ?LOC (places),

?REL (relations), ?POL (polarities), ?INF (infons), ?PAR (parameters), ?SIT (situations), and ?TYP (types). These are special objects of BABY-SIT that can be used in the same way as ordinary objects are. Moreover, they can be used to associate a type with a new object in the system. Suppose bob is an individual and s1 is a situation. Then, these objects can be declared as: I> bob: ?IND I> s1: ?SIT In BABY-SIT, situations are viewed, as usual, at an abstract level. This means that situations are sets of parametric infons, but they may be non-well-founded (circular) [2]. All situations are required to cohere. Situations (and hence the infons they support) may have spatio-temporal dimensions. A situation can have information about another which is a part of the former. BABY-SIT has a minimal situation w, called the ‘background situation’, which is a part of every other situation. Relations are categorized into two: (i) infonic relations that can be used as major constituents of infons, and (ii) non-infonic relations that can only ?ll the argument roles of infonic relations. Each infonic relation has ‘appropriateness conditions’ that determine the types of its arguments. The number of arguments that an infonic relation can take de?nes the minimality conditions for that relation. Consider the relation seeing. If we would like it to be an infonic relation with at most two arguments, the former being of type individual and the latter being of type either a situation or an individual, we write: I> sees | ?IND, {?SIT, ?IND} [1] Here, the number in square brackets indicates the minimum number of arguments that can be used with sees. Hence, sees, bob, 1 , for example, is a valid (unsaturated) infon in the system. In order for the parameters to be anchored to objects of the appropriate type, parameters must be declared to be from only one of the primitive domains. It is also possible to put restrictions on a parameter. Suppose we want to have a parameter E denoting any individual that sees situation s1. This can be done by asserting: I> E = IND1 ? sees, IND1, s1, 1 IND1 is a default system parameter of type ?IND. E is an object of type ?PAR such that if it is anchored to an object, say o1, then o1 must be of type ?IND and w |= sees, o1, s1, 1 . Parametric types are also allowed in BABY-SIT. They are of the form [P |s |= I], where P is a pa-

E. T?n and V. Akman / Situated nonmonotonic temporal reasoning with BABY-SIT Table 1 A simple comparison of PROSIT, ASTL, and BABY-SIT Computational feature PROSIT ASTL √ √ Uni?cation Type-theoretic ? ? Coherence ? ? √ Forward chaining ? √ √ Backward chaining √ Bidirectional ? Conditional constraints ? ? √ √ Partiality Parameters ? ? Type abstraction ? ? Parameter restriction ? ? Unsaturated infons ? ? √ Legend: : exists, ? : doesn’t exist, ? : partially/conceptually exists.

97

BABY-SIT

√ √ √ √ √ √ √ √ √ √ √

√

rameter, s is a situation, and I is a set of infons. The type of all situations that Bob sees can be de?ned as follows: I> ?SITALL = [SIT3 | w |= sees, bob, SIT3, 1 ] Hence, ?SITALL can be used as a type speci?er for declaration of new objects in the environment. An object of type ?SITALL, say o2, is an object of basic type ?SIT such that w |= sees, bob, o2, 1 . (o2 is of basic type ?SIT since the abstraction parameter SIT3 is a default system parameter of type ?SIT.) Variables in BABY-SIT are used in constraints and query expressions, and have scope only within the constraint or the query expression in which they appear. A variable can match any object appropriate for the argument role it appears in. For example, variables ?S and ?X in ?S |= sees, ?X, s1, 0 can only match objects of type ?SIT and ?IND, respectively. BABY-SIT allows the use contextual information which plays a critical role in all forms of behavior and communication [1]. Situations and constraints can be grouped to form a so-called ‘perspectivity (constraint) set’, which provides a computational context. Moreover, the partial nature of situations facilitates computation with incomplete information. Constraints in BABY-SIT come in three standard ?avors: forward chaining, backward chaining, and bidirectional. Assertions may activate the forward chaining mechanism of BABY-SIT which lets one derive new information via the forward chaining constraints (or bidirectional chaining constraints) of a given perspectivity constraint set. A candidate forward chaining constraint is activated whenever its antecedent is satis?ed. All the consequences are asserted if they do not yield

a contradiction in the situation into which they are asserted. New assertions may in turn activate other candidate forward chaining constraints. BABY-SIT provides a useful query mechanism. It is possible to make situated or unsituated queries in its query mode. Queries can be ‘proved’ by using the backward chaining constraints (or bidirectional chaining constraints) of a given perspectivity set. In addition to querying which situation supports what, it is also possible to ask which (particular) situation does not support an infon or a set of infons. A comparison of BABY-SIT with PROSIT and ASTL is given in Table 1.

5. YSP Various nonmonotonic formal systems have been proposed to facilitate common-sense reasoning. Situation calculus [14] has initially been used to reason about the effects of actions. Hanks and McDermott [11] describe what they call temporal projection in the framework of situation calculus as follows. Given a description of the current situation, descriptions of the effects of possible actions, and a sequence of actions to be performed, how do we predict the properties of the world in the resulting situation? Hanks and McDermott [11] applied some of the existing logics to scenarios to see whether the expected results are indeed produced. YSP is one of these scenarios, a paradigm to show how the temporal projection problem arises in logical frameworks. At some point in time, a person (Fred) is alive. A loaded gun, after waiting for a while, is ?red at Fred. What are the results of this action? One expects that Fred would die and the gun would be unloaded after the ?ring.

98

E. T?n and V. Akman / Situated nonmonotonic temporal reasoning with BABY-SIT

But Hanks and McDermott [11] demonstrate that unintended models are obtained; the gun gets unloaded during the waiting stage and ?ring the gun does not kill Fred. After Hanks and McDermott showed how existing logics fail to produce the expected results for YSP, researchers proposing new formalisms applied their methods to YSP and other similar scenarios to show how they succeed in avoiding the unintended models. Hanks and McDermott argue that a solution to the temporal projection problem should answer two questions [11, p. 409]: 1. Given a logical theory that admits more than one model, what are the preferred models of that theory (i.e., what is the preference criterion)? 2. Given a theory and preference criterion, how do we ?nd the theorems that are true in all ‘most preferred’ models? Shoham’s causal theories1 and preference criterion [17] provide a satisfactory answer to these questions. Moreover, Shoham gives an algorithm that computes the true sentences in the models preferred under his preference criterion, thus making causal theories computationally attractive. 5.1. YSP and causal theories Causal theories contain axioms to reason about the effects of actions. Proceeding in time, knowledge about the future is obtained from what is known and what is not known about the past. We will demonstrate how causal theories can be modeled in BABYSIT. Suppose that Mary loads a gun at time 0 and ?res it at Fred at time 2. We would like to reason about the effect of ?ring the gun. We provide below a possible axiomatization (using a total of 8 axioms) in causal theories.2 (1) (2) (3) (0, loads, mary, gun) (0, alive, f red) (2, f ires, mary, gun)

(5) (t, alive, f red) ∧ (t, ?f ires, mary, gun) ∧ (t, exists, air) ? (t + 1, alive, f red) (6) (t, loaded, gun) ∧ (t, ?emptied manually, gun) ∧ (t, ?f ires, mary, gun) ? (t + 1, loaded, gun) (7) (t, alive, f red) ∧ (t, loaded, gun) ∧ (t, f ires, mary, gun) ∧ (t, ?marshmallow bullets in, gun) ∧ (t, has f iring pin, gun) ? (t + 1, ?alive, f red) (8) (t, loaded, gun) ∧ (t, f ires, mary, gun) ∧ (t, has f iring pin, gun) ∧ (t, ?marshmallow bullets in, gun) ∧ (t, exists, air) ? (t + 1, hears, mary, noise) Axioms (1)–(3) are the boundary conditions. (4) is an axiom scheme saying that loading a gun makes it loaded. (5) and (6) are axiom schemes needed for persistence. For instance, (5) says that Fred remains alive unless certain conditions obtain; (6) says that the gun remains loaded unless it is manually emptied or is ?red by Mary. Axioms (6)–(8) are known as causal schemes. (8), for example, states that Mary’s ?ring a loaded gun causes her to hear a noise unless certain conditions obtain, viz. the gun has no ?ring pin, has marshmallow bullets, or there is no air. The axiom schemes (4)–(8) above must be replicated by instantiating the variable t to time points 0, 1, and 2. This actually results in a ?nite causal theory. The axioms of this causal theory should then be ordered with respect to the latest time points of the atomic base sentences on the left hand side of causal rules. The cmi model of this causal theory is computed by stepping over each axiom in ordered form and checking whether the left-hand side is satis?ed. The atomic base sentence on the right-hand side of a causal rule is asserted to the knowledge base as soon as its left-hand side is satis?ed. Therefore, this causal theory produces the expected atomic base sentences: (1, loaded, gun), (1, alive, f red), (2, loaded, gun), (2, alive, f red), (3, ?alive, f red), (3, hears, mary, noise).3

3 Here

(4) (t, loads, mary, gun) ? (t + 1, loaded, gun)

1 Cf.

Appendix A for a technical introduction to causal theories. schemes (4)–(8) are considered to be implicitly universally quanti?ed over t.

2 Axiom

and in Appendix A,

stands for TRUE.

E. T?n and V. Akman / Situated nonmonotonic temporal reasoning with BABY-SIT

99

Note that the division between - and -conditions in causal rules is somewhat unclear. Consider causal rule (8). One can start with the hypothesis that ?ring a gun causes Mary’s hearing a loud noise. To quote Shoham [18, p. 166]: “[He] might then modify that, and condition the prediction on the gun’s being loaded. Then, in time, [he] might learn about the other necessary conditions, such as there being air, the gun having a ?ring pin, and so on and so forth. Depending on the likelihood of each of these conditions and on the gravity of making wrong default assumptions, they will become either -conditions or -conditions. After a short while the theory will become suf?ciently stable so that, unless that [sic] someone were fed seriously biased data, any new modi?cations will require adding only -conditions”. Hence, we can say that the distinction between these two classes of conditions is somewhat dependent on the particular context of reasoning and that the -conditions of a causal rule are those typically true in that particular context.4 5.2. Axiomatization of YSP in BABY-SIT 5.2.1. Representing the objects We should ?rst de?ne the objects that will be used in the axiomatization of the problem. BABY-SIT Dialogue Mode provides working sessions for various modes of operation: Assertion Mode, Constraint Edit Mode, Query Mode, and (Object) Deletion Mode. However, only in Assertion Mode it is possible to directly introduce new objects to the system (Fig. 1). Assertion Mode allows the user to assert propositions which will de?ne objects in the system, establish hierarchies between situations, or add infons to the existing situations. We start with the introduction of relations such as alive, loads, fires, etc. that will hold among objects. For example, fires is de?ned as follows: I> fires | ?IND, ?IND [2] Its arguments must be ?lled by objects of type ?IND since the minimality conditions of the relation is given as 2.5 Then, we de?ne individuals such as fred, mary, etc. Figure 2 shows the declaration of these objects in Assertion Mode.

We consider each snapshot in time as a situation. For instance, Mary’s loading the gun and Fred’s being alive at time 0 form a state. Any inferred information about future will be collected in a new state. For this reason, we create a situation s0 as the initial state and assert the facts that Mary loads the gun and that Fred is alive in s0. As soon as s0 is declared as a situation, it appears in BABY-SIT Situation Browser (SBR) (Fig. 2). SBR displays situation tree structures graphically. Each situation is shown as a node labeled by the name of that situation. A situation is always displayed at a lower level than its subsituation and a line is drawn from the situation to its subsituation to indicate the tree hierarchy. Each line ends on the supersituation with a ?lled box. Hence, each situation at the lower parts of SBR is a supersituation with respect to the ones it is connected to in this way. Each time a new situation is created via assertions either in Assertion Mode or during chaining, it is displayed on SBR. Any change in the current situation tree hierarchy is also re?ected to SBR. SBR provides an interactive environment so that the user can manipulate the situation tree structure, view infons, add/delete infons, anchor parameters of infons, and issue queries in speci?c situations. By clicking on a situation node on SBR, the user can perform various menu-driven operations (Fig. 3). 5.2.2. Implementing the axiom schemes The next step in the axiomatization of YSP includes writing equivalent BABY-SIT constraints for axiom schemes (4)–(8). De?ning objects and asserting infons into situations form a description. This description evolves as new assertions are made. On the other hand, it is possible in BABY-SIT to make inference over a given description by the help of constraints and hence carry the current description to new stages. There are mainly three types of constraints in BABYSIT: forward chaining, backward chaining, and bidirectional chaining constraints. Forward chaining constraints enable one to infer new information from the existing information, alter the environment, and act accordingly. (For this reason, these constraints may be called ‘action’ constraints.) We will implement the axiom schemes of YSP in the form of forward chaining constraints. Hence, we elaborate on this constraint type in the sequel and de?ne some terms that are employed by BABY-SIT constraints. A schematic infon is an infon that contains at least one variable as either its major constituent or one of its minor constituents. A schematic compound infon

4 The reader may refer to [22] and [21] for a discussion on various aspects of causal reasoning in Shoham’s model. 5 We have used only basic types in our declarations in order not to diverge from the essence of YSP. Clearly, it is also possible to de?ne complex types built out from the basic types.

100

E. T?n and V. Akman / Situated nonmonotonic temporal reasoning with BABY-SIT

Fig. 1. Available operations in Dialogue Mode.

Fig. 2. Object declarations for Yale Shooting Problem.

Fig. 3. Situation Browser allows menu-driven operations on situations.

E. T?n and V. Akman / Situated nonmonotonic temporal reasoning with BABY-SIT

101

is a collection of infons, in which there exists at least one schematic infon. A schematic infonic proposition is an expression of the form s {|=, |=} Γ, where s is either a situation or a variable, and Γ is either a compound infon or a schematic compound infon. The ones having the form s |= Γ are called positive schematic infonic propositions; those having the form s |= Γ are called negative schematic infonic propositions. A schematic infonic condition is of the form s : Γ, where s is either a situation or a variable, and Γ is either a compound infon or a schematic compound infon. A forward chaining constraint has two constituent parts: the body and the background conditions. The body of a constraint has the form: antecedent1, . . . , antecedentn ? consequent1, . . . , consequentm, i n, is a (positive where each antecedenti, 1 or negative) schematic infonic proposition and each consequentj , 1 j m, is a positive schematic infonic proposition. The background conditions of a constraint has the form: condition1, . . . , conditionk , where each conditionl, 1 l k, is a schematic infonic condition. (The background conditions may be empty.) Whenever the propositions in the antecedent and the background conditions of a forward chaining constraint succeed, all of the propositions in its consequent are asserted. Each constraint has a unique identi?er associated with it and it must belong to a group. Inferences can be drawn with respect to a given group of constraints. These groups are called perspectivity (constraint) sets. For example, the following is a forward chaining constraint named FALLING-BLOCK under the perspectivity set NATURAL-LAW-PERSPECTIVE, and states that blocks drop if not supported:

NATURAL-LAW-PERSPECTIVE: FALLING-BLOCK:

while ?B and ?C can have values of some type appropriate for the argument roles of block and drops, and supports, respectively.6 Since the supporting situation variables in the antecedent and consequent parts of the constraint are different, a new situation, in which the block drops, is created when the constraint is activated. In this way, a state change for the block of concern is obtained. FALLING-BLOCK is associated with a background condition. A background condition is, in fact, an assumption which is required to hold for a constraint to be eligible for activation. This constraint can become a candidate for activation only if it is the case that w |= exists, gravity, 0 , i.e., if there is no information as to the absence of gravity in the background situation. Each conditional constraint in BABY-SIT can be reduced to an unconditional one by providing a semantically equivalent negative schematic infonic proposition for each condition in the background conditions of the constraint. For example, an equivalent unconditional constraint for FALLING-BLOCK is:

NATURAL-LAW-PERSPECTIVE: FALLING-BLOCK:

?S1 |= block, ?B, 1 , ?S1 |= supports, ?C, ?B, 1 , w |= exists, gravity, 0 => ?S2 |= drops, ?B, 1 . Before examining the representation of YSP axiom schemes (1)–(8) in BABY-SIT, we provide some rules governing the functionality of the forward chaining mechanism: – The forward chaining mechanism is initiated either when the user tells the system to do so or by asserting a new proposition into the system. – Forward chaining can be performed with respect to a given perspectivity set, i.e., by using the forward chaining constraints in a speci?c perspectivity set. Otherwise, the default system constraints are used. – To ?nd the candidates for activation, forward chaining constraints are examined according to the ‘constraint ordering’. The criterion for constraint ordering used by the forward chaining mechanism is ‘constraint type’. ‘Non-action’ constraints are considered ?rst, and then ‘action’ constraints.

6 Note that ?S1 |= block, ?C, 1 need not appear in the antecedent of the constraint, for the block may well be supported by any other object, e.g., the table.

?S1 |= block, ?B, 1 , ?S1 |= supports, ?C, ?B, 1 => ?S2 |= drops, ?B, 1

BACKGROUND-CONDITIONS:

w: exists, gravity, 1 Here, ?S1, ?S2, ?B, and ?C are variables. ?S1 and ?S2 can only be assigned objects of type ?SIT

102

E. T?n and V. Akman / Situated nonmonotonic temporal reasoning with BABY-SIT

– Negative schematic infonic propositions in the antecedent part of a forward chaining constraint are always evaluated last, with respect to the positive schematic infonic propositions in that part. – The consequents of an activated forward chaining constraint are asserted into the system only if they are valid propositions (i.e., if the arguments of infons are of appropriate type and the assertion of the propositions does not produce an incoherent situation). For axiom schemes (4)–(8) in YSP, we can write equivalent forward chaining constraints in BABY-SIT. -conditions of these axiom schemes can be represented by positive schematic infonic propositions while their -conditions are assumptions and hence can be represented by background conditions in constraints. Consider axiom scheme (8). By a direct transformation, we obtain the corresponding BABY-SIT forward chaining constraint: ?S1 |= { loaded, ?G, 1 , fires, ?M, ?G, 1 } => ?S2 |= hears, ?M, noise, 1 , ?S1 |= precedes, ?S1, ?S2, 1 w: exists, air, 1 ?S1: { has-firing-pin, ?G, 1 , marshmallow-bullets-in, ?G, 0 } The “-” sign separates the body and the background conditions of the constraint. The constraint simply states the following: “if g is loaded in a situation s1 , and is ?red by m in that situation, m hears a noise in a situation s2 that temporally succeeds s1 , given that the assumptions (existence of air, g’s having a ?ring pin, but not being loaded with marshmallow bullets) hold”. Since these assumptions are required to hold in s1 , we use the same supporting situation variable in the body and the background conditions of the constraint. However, we have required existence of air in the background situation w. Note that any infon supported by w is also supported by other situations since it is, by default, a part of every other situation. Since we use a situation variable (?S2) that only appears in the consequent part of the forward chaining constraint, activating this constraint would create a new situation and assert the instantiated form of hears, ?M, noise, 1 into that situation. Now consider axiom scheme (5). The corresponding BABY-SIT forward chaining constraint can be written as:

?S1 |= alive, ?F, 1 => ?S2 |= alive, ?F, 1 , ?S1 |= precedes, ?S1, ?S2, 1 w: exists, air, 1 ?S1: { fires, ?M, gun, 0 , precedes, ?S3, ?S1, 0 } This constraint says “if f is alive in a situation s1 , it will be alive in a situation s2 that temporally succeeds s1 , given that there exists air and that another object m does not ?re the gun.” One point worth mentioning here is the inclusion of an assumption that there should be no situation that precedes the current reasoning situation s1 . This assumption is needed to avoid reasoning over the same situation repeatedly. As for the axiom scheme (4), it could have been represented in a similar manner. However, we have implemented it as a forward chaining constraint with no state transition, i.e., loading the gun does not cause a change of state: ?S1 |= loads, ?M, ?G, 1 => ?S2 |= loaded, ?G, 1 Axiomatization of YSP in the form of BABY-SIT constraints is shown in Fig. 4, where constraints (R5)–(R1) in descending order correspond to axiom schemes (4)–(8) in ascending order. It may be that there appear to be two different situations that immediately succeed a situation. These two situations, however, must represent a unique snapshot in time. For this reason, they must be uni?ed (made into a single situation). We achieve this by introducing new constraints, R6 and R7, which make one of these situations a part of the other. When an infon of the form make-part-of, s1 , s2 , 1 is asserted, s1 becomes a subsituation of s2 . The relation part-of is automatically asserted into s2 . s2 cannot be the background situation since it is always a subsituation of other situations in the system. Therefore, if there are two situations s2 and s3 that succeed situation s1 , constraint R7 uni?es s2 and s3 (by making s3 a part of s2 ). Similarly, if there are two situations s1 and s2 (where one is a part of another) and if these situations have successors s3 and s4 , respectively, then constraint R6 uni?es s3 and s4 (Fig. 4). 5.2.3. Inferencing over situations Assertion Mode Setup of BABY-SIT serves as a control unit for the evaluation of the expressions asserted in Assertion Mode. There are four possible actions that can be controlled by the user via Assertion Mode Setup (Fig. 5):

E. T?n and V. Akman / Situated nonmonotonic temporal reasoning with BABY-SIT

103

Fig. 4. The constraints for Yale Shooting Problem.

Fig. 5. A view from Assertion Mode Setup.

1. Anchoring the parameters. If this option is enabled, each parameter in the asserted expression is replaced by a corresponding individual according to the anchoring de?ned in the anchoring situation. The anchoring situation can be speci?ed by the user on the corresponding slot of the Assertion Mode Setup template (i.e., anchoring situation before assertion in Fig. 5). (The anchoring situation defaults to w.)

2. Making inferences with the existing information. The proposition asserted can be used to make inferences over the existing information by employing a set of forward chaining constraints. An existing perspectivity set name should be typed by the user on the corresponding slot of the Assertion Mode Setup template (i.e., perspectivity constraint set in Fig. 5). Otherwise, the system perspectivity set is used. In either

104

E. T?n and V. Akman / Situated nonmonotonic temporal reasoning with BABY-SIT

Fig. 6. YSP: After Mary’s loading the gun.

case, the forward chaining constraints of the current perspectivity set are employed in drawing inferences. 3. Using a different perspectivity set. The antecedents of forward chaining constraints in the current perspectivity set are normally proved with respect to the backward chaining constraints in this set. Additionally, the backward chaining constraints in another perspectivity set can be used for this task. 4. Verifying antecedents. The antecedents of a candidate forward chaining constraint may be veri?ed prior to its activation. In our example, we only need the simple inference mechanism of the system, and hence use the second option above. We ?rst set the current forward chaining perspectivity set to GUNFIRE. Then asserting the fact that Mary loads the gun causes constraint R5 to be activated and the gun gets loaded in s0 (Fig. 6). Forward chaining over the existing information creates, by activating constraint R3, a new situation R3-1 where the gun remains loaded and then creates, by activating R4, another situation R4-2, where Fred is alive (Fig. 7). Constraint R6 uni?es these situations in the next activation of forward chaining (Fig. 8). Activation of forward chaining once more creates sit-

uations R3-3 and R4-4 by reasoning over R3-1 and R4-2, respectively (Fig. 9). Subsequent activations of forward chaining unify new states and then create new states by forming new situations in a similar manner. Assume that we iterate forward chaining twice and assert the fact that Mary ?res the gun. Then two new situations R2-7 and R1-8 are created (by R2 and R1), where Fred ceases to be alive and Mary hears a noise, respectively (Fig. 10). However, if we had asserted w |= exists, air, 0 prior to Mary’s ?ring the gun, a new situation, R2-9, would be created, where Fred would be dead but Mary would not be able to hear a noise (Fig. 11). 5.2.4. Time-dependency in causal computations Shoham’s algorithm computes the atomic base sentences known in all cmi models of a ?nite causal theory. Thus, his approach has a problem when the causal theories contain axiom schemes: computation is time-dependent because the size of the corresponding ?nite causal theory depends on the ‘time span’ of the theory. However, it is possible in BABY-SIT to represent both ?nite causal theories and causal theories having axiom schemes. In YSP, except boundary conditions, BABY-SIT contained axiom schemes.

E. T?n and V. Akman / Situated nonmonotonic temporal reasoning with BABY-SIT

105

Fig. 7. YSP: After the ?rst iteration of forward chaining.

Fig. 8. YSP: After the second iteration of forward chaining.

Note that in either case one must draw inferences by beginning from some initial time t0 and moving forward to times t0 + 1, t0 + 2, and so on. But one may wish to ‘jump into conclusions’ about the consequences of an action. For example, one may want to directly observe the effect of Mary’s loading and/or ?ring a gun. This can also be done in BABY-SIT with a slight modi?cation of the model presented above. We now describe this modi?cation. In temporal projection scenarios, there exist two types of axiom schemes. The ?rst type takes care of the persistence of facts, permitting inferences about what remains unchanged. For example, if you load a gun, it will stay loaded unless you ?re or empty it.

Such schemes are called persistence axiom schemes. In YSP, (5) and (6) are persistence axiom schemes. The second type represents what changes occur in the environment. Such schemes are called causal axiom schemes. More speci?cally, these allow one to infer what kind of changes actions bring about. In YSP, (4), (7), and (8) are causal axiom schemes. In order to be able to jump into conclusions for YSP, we divide BABY-SIT constraints into two with respect to this categorization. Constraints R1, R2, and R5 form a perspectivity set called CAUSAL, and constraints R3 and R4 are collected into a perspectivity set called PERSIST. We also put R6 and R7 into a separate perspectivity set called UNIFY. Given an initial

106

E. T?n and V. Akman / Situated nonmonotonic temporal reasoning with BABY-SIT

Fig. 9. YSP: After the third iteration of forward chaining.

Fig. 10. YSP: After Mary’s ?ring the gun.

Fig. 11. YSP: After Mary’s ?ring the gun in vacuum condition.

E. T?n and V. Akman / Situated nonmonotonic temporal reasoning with BABY-SIT

107

situation, forward chaining over PERSIST would produce facts that remain unchanged in the next situation in which one would reason about the effects of an action via CAUSAL. Forward chaining over UNIFY must be needed just after forward chaining over PERSIST to unify the results of persistence (into a single state). Therefore, the order of forward chaining perspectivity sets to determine the consequences of an action should be as follows: PERSIST, UNIFY, CAUSAL. We form the initial situation s0 by asserting the fact that Fred is alive. We then set the forward chaining perspectivity set to CAUSAL and assert the fact that Mary loads the gun. R5 is immediately activated and the gun gets loaded in s0. Setting the current perspectivity set to PERSIST and enabling forward chaining causes R3 to be activated and creates a new situation R3-1, where the gun remains loaded. At the same time R4 is activated and another situation R4-2 is created, where Fred is alive. Then forward chaining over UNIFY forms a unique state with situations R3-1 and R4-2. Finally, setting the perspectivity set to CAUSAL and asserting the fact that Mary ?res the gun in R3-1 activate constraints R1 and R2. Hence, two new situations R1-4 and R2-3 are created where Mary hears a noise and Fred ceases to be alive, respectively.7

Acknowledgments We owe special thanks to the Editor-in-Chief for his encouragement and invaluable advice. Comments of an anonymous referee of the journal have also been extremely useful and led to a major revision of the initial manuscript. As usual, all the remaining inadequacies are our own.

Appendix A: Shoham’s causal theories This appendix is summarized from Shoham’s doctoral dissertation [18]. It may be skipped by readers already knowledgeable about this work. The standard monotonic logic on which Shoham’s causal theories are based is called the logic of temporal knowledge (TK). The syntax and semantics of TK are given below. Let P be a set of primitive propositions, T V a set of temporal variables, T C = Z (integers: the structure of time), and U = T C ∪ T V . Well-formed formulae (wff) are de?ned as follows: 1. If u1 , u2 ∈ U and p ∈ P , then u1 = u2 , u1 u2 , and (u1 , u2 , p) are wff. 2. If ? is a wff, then so is ??. 3. If ?1 and ?2 are wff, then so is ?1 ∧ ?2 . 4. If ? is a wff, then so is ?. ? stands for “? is known”. We de?ne ≡ ? ??. ? stands for “? is not known to be false”. 5. If ? is a wff and v ∈ T V , then ?v? is also a wff. Some abbreviations: (t1 , t2 , p) is shortened as (t1 , t2 , p), ? (t1 , t2 , p) as (t1 , t2 , ?p), (t1 , t2 , p) as (t1 , t2 , p), and ? (t1 , t2 , p) as (t1 , t2 , ?p). Finally, (t, p) abbreviates (t, t, p). A Kripke interpretation (κ) is a pair W, M , where W is a nonempty universe of possible worlds and M is a meaning function such that M : P → 2W ×Z×Z . A variable assignment is a function va : T V → Z. A valuation function (val) is such that val(u) = va(u) if u ∈ T V , and val(u) = u if u ∈ T C. A Kripke interpretation κ and a world ω ∈ W satisfy a formula ? under va (written κ, ω |= ?[va]) according to the following de?nition: 1. κ, ω |= u1 = u2 [va] iff val(u1 ) = val(u2 ). κ, ω |= u1 u2 [va] iff val(u1 ) val(u2 ). κ, ω |= (u1 , u2 , p)[va] iff ω, val(u1 ), val(u2 ) ∈ M (p). 2. κ, ω |= ??[va] iff κ, ω |= ?[va].

6. Conclusion We have shown how AI problems that necessitate a nonmonotonic temporal approach can be handled in the situation-theoretic computational framework of BABY-SIT. Speci?cally, we have considered the Yale Shooting Problem and have implemented the wellknown approach of Yoav Shoham. The conceptual clarity gained by the adoption of situation theory as a knowledge representation scheme makes its presence strongly felt in our handling of YSP. Our immediate goal is to apply situation theory to other representation problems in AI.8 On a more general note, we believe that computational aspects of situation theory call for deeper investigation. Although the situation-theoretic systems reviewed in this paper are in their infancy, they are promising in terms of applicability in AI [25].

7 These two new situations correspond to R1-8 and R2-7, respectively, in Fig. 10. 8 For a preliminary attempt in this vein, the reader is referred to [9] which studies puzzles of knowledge/belief in PROSIT.

108

E. T?n and V. Akman / Situated nonmonotonic temporal reasoning with BABY-SIT

3. κ, ω |= ?1 ∧?2 [va] iff κ, ω |= ?1 [va] and κ, ω |= ?2 [va]. 4. κ, ω |= ?[va] iff κ, ω |= ?[va] for all ω ∈ W . (Therefore, we are able to write κ |= ?[va] without fear of ambiguity.) 5. κ, ω |= ?v?[va] iff κ, ω |= ?[va ] for all va that agree with va everywhere except possibly on v. A Kripke interpretation κ and a world ω ∈ W are a model for a formula ? (written κ, ω |= ?) if κ, ω |= ?[va] for any variable assignment va. A wff is satis?able if it has a model, and valid if its negation has no model. ?1 entails ?2 (written ?1 |= ?2 ) iff ?2 is satis?ed by all models of ?1 . Base formulae are those wff containing no occurrence of the modal operators. The latest time point (ltp) of a base formula is the (chronologically) latest time point mentioned in it. κ2 is chronologically more ignorant than κ1 (written κ1 ?ci κ2 ) if there exists t0 such that 1. For any base sentence ? (whose ltp t0 ), if κ2 |= ? then also κ1 |= ?. 2. There exists a base sentence ? (whose ltp is t0 ) such that κ1 |= ? but κ2 |= ?. κ is said to be a chronologically maximally ignorant (cmi) model of ? if κ |=?ci ?, i.e., if κ |= ? and there is no other κ such that κ |= ? and κ ?ci κ . The logic of chronological ignorance, CI, is the nonmonotonic logic obtained by associating the preference relation ?ci with TK. Base sentences in CI are those sentences containing no occurrence of the modal operators, i.e., sentences that refer directly to the real world and not to a knowledge of it. Atomic base sentences are of the form (t1 , t2 , p) or (t1 , t2 , ?p). A causal theory Ψ is a theory in CI, in which all sentences have the form Φ ∧ Θ ? ?, where (in the following [?] means that ? may or may not appear): 1. ? = (t1 , t2 , [?]p). n 2. Φ = i=1 ?i , where ?i is an atomic base sentence whose ltp ti < t1 . 3. Θ = m j=1 ?j , where ?j is an atomic base sentence whose ltp tj < t1 . 4. Φ or Θ may be empty. A sentence in which Φ is empty is called a boundary condition. Other sentences are called causal rules. 5. There is a time point t0 such that if Θ ? (t1 , t2 , [?]p) is a boundary condition, then t0 < t1 .

6. There do not exist two sentences in Ψ such that one contains (t1 , t2 , p) on its left-hand side and the other contains (t1 , t2 , ?p) on its left-hand side. 7. If Φ1 ∧ Θ1 ? (t1 , t2 , p) and Φ2 ∧ Θ2 ? (t1 , t2 , ?p) are two sentences in Ψ, then Φ1 ∧ Θ1 ∧ Φ2 ∧ Θ2 is inconsistent. An essential property of a causal theory is that it has cmi models, and in all of these the same set of atomic base sentences is known [18, pp. 112–113].

References

[1] [2] V. Akman and M. Surav, Steps toward Formalizing Context, AI Magazine 17(3) (1996), 55–72. J. Barwise and J. Etchemendy, The Liar: An Essay on Truth and Circularity, Oxford University Press, New York, NY, 1987. J. Barwise and J. Perry, Situations and Attitudes, MIT Press, Cambridge, MA, 1983. A.W. Black, An approach to computational situation semantics, PhD thesis, Department of Arti?cial Intelligence, University of Edinburgh, Edinburgh, UK, 1993. J. Borota, M. Frank, J. Fry, A. Ito, H. Nakashima, S. Peters, M. Reilly and H. Sch¨ tze, The PROSIT Language, Veru sion 1.0. Manuscript, Center for the Study of Language and Information, Stanford, CA, 1994. R. Cooper, Three Lectures on Situation Theoretic Grammar, in: Natural Language Processing, number 476 in Lecture Notes in Arti?cial Intelligence, M. Filgueiras, L. Damas, N. Moreira and A.P. Thom? s, eds, Springer-Verlag, Berlin, a Germany, 1991, pp. 102–140. K. Devlin, Logic and Information, Cambridge University Press, Cambridge, UK, 1991. F. Dretske, Knowledge and the Flow of Information, MIT Press, Cambridge, MA, 1981. M. Ersan and V. Akman, Situated modeling of epistemic puzzles, Bulletin of the IGPL 3 (1995), 51–76. J.E. Fenstad, P.-K. Halvorsen, T. Langholm and J. van Benthem, Situations, Language, and Logic, Reidel, Dordrecht, Holland, 1987. S. Hanks and D.V. McDermott, Nonmonotonic logic and temporal projection, Arti?cial Intelligence, 33 (1987), 379– 412. KEET M , Knowledge Engineering Environment Software Development System, Version 4.1. IntelliCorp, Inc., Mountain View, CA, 1993. Y. Lesp? rance, Toward a computational interpretation of site uation semantics, Computational Intelligence 2 (1986), 9– 27. J. McCarthy and P.J. Hayes, Some philosophical problems from the standpoint of arti?cial intelligence, in: Machine Intelligence, B. Meltzer and D. Michie, eds, Edinburgh University Press, Edinburgh, UK, 1969, pp. 463–502. H. Nakashima, S. Peters and H. Sch¨ tze, Communication and u inference through situations, in: Proceedings of the Third Conference on Arti?cial Intelligence Applications, IEEE Computer Society Press, Washington, DC, 1987, pp. 76–81.

[3] [4]

[5]

[6]

[7] [8] [9] [10]

[11]

[12]

[13]

[14]

[15]

E. T?n and V. Akman / Situated nonmonotonic temporal reasoning with BABY-SIT H. Nakashima, H. Suzuki, P.-K. Halvorsen and S. Peters, Towards a computational interpretation of situation theory, in: Proceedings of the International Conference on Fifth Generation Computer Systems, Institute for New Generation Computer Technology, Tokyo, Japan, 1988, pp. 489–498. [17] Y. Shoham, Chronological ignorance: experiments in nonmonotonic temporal reasoning, Arti?cial Intelligence 36 (1988), 279–331. [18] Y. Shoham, Reasoning About Change: Time and Causation from the Standpoint of Arti?cial Intelligence, MIT Press, Cambridge, MA, 1988. [19] Y. Shoham and D.V. McDermott, Problems in formal temporal reasoning. Arti?cial Intelligence 36 (1988), 49–61. [20] J.P. Stillman and R. Arthur, Tachyon: a model and environment for temporal reasoning, in: National Conference on Arti?cial Intelligence: Workshop on Implemented Temporal Reasoning, San Jose, CA, 1992. [21] R. Sun, Integrating Rules and Connectionism for Robust Commonsense Reasoning, Wiley, New York, NY, 1994. [16] [22]

109

[23]

[24] [25]

[26]

E. T?n and V. Akman, Computing with causal theories. International Journal of Pattern Recognition and Arti?cial Intelligence 6(4) (1992), 699–730. E. T?n and V. Akman, BABY-SIT: a computational medium based on situations, in: Proceedings of the 9th Amsterdam Colloquium, P. Dekker and M. Stokhof, eds, Institute for Logic, Language, and Computation, University of Amsterdam, Amsterdam, Holland, 1993, pp. 665–681. E. T?n and V. Akman, Computational situation theory, ACM Sigart Bulletin 5(4) (1994), 4–17. E. T?n and V. Akman, Information-oriented computation with BABY-SIT, in: Language, Logic, and Computation: Volume 1, number 58 in CSLI Lecture Notes, J. Seligman and D. Westerst? hl, eds, Center for the Study of Language and a Information, Stanford, CA, 1996, pp. 19–34. E. T?n, V. Akman and M. Ersan, Towards situation-oriented programming languages, ACM Sigplan Notices 30(1) (1995), 27–36.