A State Logic for the Representation of Natural Language Based Intelligent Systems

A STATE L,JGIC FOR TJIE "'lliP'1F:SENTATIO:I OF NATURAL LA:.1GUAGr::; BASED I NTE!"LIGS>JT SYSTE:IS

Camilla B. Schwind Technische Universittit ~Unchen :1unich, FRG

_Su:n:nary

The work described herein introduces a ge­ neral logic based formalism for the acti­ ons of an intelligent syste~ understanding natural language sentences, executing com­ mands and answering questions.

natural language

translation

state logic derivations formulae ~=====~-·

interpretati-on

of the logic

Kripke-type zation

models characteri-~=====:: ·

loqical axioms

non-lorricat axioms

The heart of this formal system is a sta­ te (or tense) logic containing special operators for immed iately next and prece­ din'] states (+,-) as well as for all fu­ ture states (F) and all past states (P) .

Natural language texts are analysed syn­ tactically and transduced into state lo­ gic formulae by an attributed grammar (in the same way as descri~ed by Schwind) .

The state logic is formalized by a set of logical axioms and derivation rules for which completeness has been proven . Simi­ lar systems have also been mentioned by Rescher. But in usual tense logic systems, the structure of tense has been studied only as to its "pure logical" properties. In intelligent systems however, we need theorems about the non-logical properties of state changes. The tense structure of a world is determined by changes within the world ,.,hich affect the non-loqical sym­ bols of the world, i.e. the functions or predicates: If a robot takes a block "a" lying on a block "b", then this causes a change of the world (i.e. a state transi­ tion) with the meaning of the predicate symbol ON changing. Such non-logical chan­ ge descriptions are incorporated into our formal system. A model for the state lo­ gic is given by a set of classical struc­ tures M and a binary relation R on M where s R S 1 means that the st~te of the worlds i~ediately precedes the state S 1 · Truth values are assigned to formulae de­ pending on the state of the 'VTOrld in which the formula is evaluated. And the state operators take into account the truth va­ lue of a formula in some other states

'llhich can be "reached" from the actual state. To represent the knO"<lledge incor­ porated in an intelligent system hy such Kripke-type models we assign a non~logical interpretation to state transitions. The very general model of Kripke-structures is used in such a way that the relation 'R bears a non-logical r.1eaning. For t'l'm s~ructures A and A 1 s R S 1 holds iff the ··,.,rorld" s A 1 8 is ob£ained from the world A as thesresult of an action which can be ~xecutecl within A . V7hat actions can be executed within asworld depend on the extensions of the non-logical symbols. On natural language level actions are verbs. The execution of an action has con­ sequences on the extensions of the non­ logical symbols of the world, i.e. a structure is subject to some change when­ ever the action described by the verb is executed in it. If somebody takes a thing the position of that thinq changes, i.e. the extension of the predicate symbols OH, BEHirm etc. and the extension of the verb predicate symbol HOLD c.hanges, because the person holds the thinq nov1. There are al­ so preconditions for the execution of an action; "a takes b" is only possible if "a" does not yet hold anything and if "b" has a position such that it can be taken, i.e. there is nothing on qb". We describe both the preconditions and the consequen­ ces of an action by non-logical axioms. And the appropriate structure must have the property that in whatever state all the conditions of an action hold there must he some Eollm.,rin'] state in which its consequences are realized.

Example: Action verb "take" Precondition axiom (PA) TAKE x y..,. HAHD x ,, THING Y-"lHOLD x z -'\I ON z y This means: x can take y iff x is a hand and y is a thing and x does not hold any other object and there is nothing on y .

Execution axiom (EA)

TAKE x y~/+ l [}I OLD x YA-, ON y z] This means: If x takes y then there is an i runec1iately follovTing state such that x holds y and y is not lying on anything.

We could only describe a small part ot the possibilities of our formalism here. We actually develop application examples of very different types: one for the ana­ lysis of tales and one for traffic.

P.Hayes, A logic of Actions . r1achine In­ tell. 6. pp.495-52o. Ed. B.Meltzer + D.Michie. Edinb. Univers. Press (1971) '1. .1-1insky , A Framework for Representing Knowledge . ~.I.T.A.I . Memo 3o6 (6.1974) N.'Rescher + A.Urquhart, Temporal logic. Springer-Verlag, Nien 1971

C. Schwind, Generating Hierarchical Seman­ tic Networks from Natural Language Dis­ course. Proceed. of the IJCAI4, (9.1975) T.Winograd, Understanding Natural Langua­ ge. Academic Press (1972)