--- title: "Centered Logic: The Role of Entity Centered Sentence Representation in Natural Language Inferencing" authors: - "Aravind K. Joshi" - "Steve Kuhn" doi: "" url: "https://ijcai.org/proceedings/1979/95" pdf: "https://ijcai.org/proceedings/1979/0095.pdf" venue: "Proceedings of the Sixth International Joint Conference on Artificial Intelligence" year: 1979 pages: "" track: "" keywords: --- # Centered Logic: The Role of Entity Centered Sentence Representation in Natural Language Inferencing Aravind K. Joshi, Steve Kuhn *Proceedings of the Sixth International Joint Conference on Artificial Intelligence*. ## Abstract We will briefly describe the role of entity centered structure (ECS) of sentences in natural language inferencing. The basic structure of sentences in discourse, generally sin9les out an entity, to be called center, among all those which are the arguments of the main predicate. ECS makes n-ary predicates look like monadic by temporarily masking their structure, thereby affecting the relative ease with which certain inferences are made and information is retrieved. This short paper deals with a preliminary formulation of a system desi9ned to capture these ideas and contains several examples of how some natural language inferences can be represented in the system . Formal properties of the system are under investigation. ## Full text ## CENTERED LOGIC: THE ROLE OF ENTITY CENTERED SENTENCE REPRESENTATION ## IN NATURAL LANGUAGE INFERENCING* Steve Kuhn Department of Philosophy Georgetown University Washington, D.C. 20057 U.S.A . Aravind K. Joshi Department of Computer and Information Science R.268 Moore School, University of Pennsylvania Philadelphia, PA 19104 U.S.A . ABSTRACT : · We will briefly describe the role of entity centered structure (ECS) of sentences in natural language inferencing. The basic structure of sentences in discourse, generally sin9les out an entity, to be called center, among all those which are the arguments of the main predicate. ECS makes n-ary predicates look like monadic by temporarily masking their structure, thereby affecting the relative ease with which certain inferences are made and information is retrieved. This short paper deals with a preliminary formulation of a system desi9ned to capture these ideas and contains several examples of how some natural language inferences can be represented in the system. Formal properties of the system are under investigation. 1. Inttuouction: A uniform mechanism that s ubsumes all inference mechanisms involved in problem solving in general may be adequate to characterize inferences in language in some sense (analogy: Turing machines characterize all co~putable functions); however, it will not shed much light on those mechanisms that are language relevant and presumably contribute to the efficiency of the inferencing process. In a natural language inferencing system, we are concerned with not just what inferences are made, but also how they are made (with what ease, for example). This paper is motivated by these considerations . In particular, we will be concerned with the fact that the basic struc­ ture of natural language· sentences in discourse, generally, singles out an individual (entity), to be called the center, among all those which are the arguments-C>r-the main predicate. Our notion of center roughly corresponds to the linguistic notions of focus (in contrast to presuprosition) and comment (in contrast to topic). We have deliberately used a new term in order to avoid precise identification with those notions and the possible resultant misunder­ standing. These linguistic notions are somewhat vague and there is a great deal of confusion in the literature; further, the term "focus" is used used in the AI literature in yet another sense. For the interested reader, we recommend [4], [7], and [8) for the linguistic notions, and [5], [6] for the AI notions. * This w0rk was nartially supported by ~SF Srant HCS 78-1~466 and a ~rant fro~ the Sloan Foundation to the University of Pennsylvania. We are indebted to the valuable comments of an unknown referee and a self-identified referee ("artin Kay). These have helped us greatly in i~0roving both the style and content of this pape,.. \/e a 1 so 1·1ant to thank Ell en Pri nee anci Bonnie Webber for very Profitable discussions. The notion of center is a discourse construct; it may on occaSTOnlmap on the subject of the sentence, but this need not be the case always. Such a representation can be regarded as an ascription of a property to a single individual, though the property itself may involve other individuals. For instance, in a particular context, JOHN may be the center of the sentence as in (l)~OHN HIT BILL. Underlining designates the center. It may help the reader to represent (1) in the extraposed form where the center is more clearly indicated as in (2) IT IS JOHN WHO HIT BILL. In another context, the center may be BILL, as in (3) JOHN HIT RILL. (IT IS BILL HHOM JOHN HIT.) More formally,--wewill represent (1) and (3) respectively as (4) and (5): (4)(JOHN x) (HIT x BILL) or (jx) (H x b); (5) (BILL y) (HIT JOHN y) or (jy) (H j y). This entity centered structure (ECS) of natural language sentences is in sharp contrast to the structure of the usual formal langua~e sentences which express relations among several individuals without singling out any one in particular. (Our use of the term ECS is very limited, pre­ cisely as defined here. For a wider use of this term in the context of knowledge representation (KR), see [2] and [1].) ECS makes it easier to see the rough logical form of the sentence. n-ary predicates seem to be monadic because part of their structure is temporarily hidden (see 4 and 5 above). An individual which is not centered is essentially ignored. It can be brought into consideration only by being made a center. ECS seems to affect the relative ease with which certain inferences are made and information is retrieved. For example, given (1) IT WAS JOHN HHO HIT BILL, (jx) (H x b), it is easier to answer (2) HHO HIT BILL? (ix?) {H x b) than (3) WHOM DID JOHN HIT? (~y?) (H j y). (See also Examples 1 and 2 in Section 5. ) It is well known that inferencing is much easier in monadic predicate logic (MPL) than in full predicate logic, and that it is decidable (see, for example, [3]) . It is also obvious that MPL is inadequate to handle all inferences in natural language. Nevertheless, a great deal of inferencing in natural language seems to proceed as if we are dealing with monadic predicates. It is of interest to see what mechanisms can be added to MPL which would give the added power, yet maintain the essential flavor of monadic calculus. He have been investigating some systems of this nature from the points of view of (i) their ability to capture some key properties of inference mechanisms at work in language, and (ii) their formal properties, to the extent these formal results give some in­ ~ignt into the structure and function of discourse constructs. In Sections 2, 3, and 4 we have presented a tentative formulation of Centered Logic (CL), and in Section 5 we have presented some sample derivations, followed by some discussion of the power of CL and some open questions. 2\_·--~~n\_9\_!!\_\_~ The forma 1 1 anguage for centered logic differs from that of predicate logic in that the individual constants serve as variable binders in the "basic sentences," e.g., we write (jx) (H x m) for IT HAS JOHN HHO HIT MARY, and (mx) (H j x) for IT WAS Marv t~HOM JOHN HIT. For the purposes of this pap~a simpler notation would have sufficed. Ours was chosen with an eye towards future treatments of intensional predicates. We want to be able to distinguish between, e.g., (ax) (Bxad) (Anastasia is such that she believes Anastasia is Grand Duchess of Russia) and (ax) (Bxxd) (Anastasia is such that she believes she is Grand Duchess of Russia.) In addition, we allow complex sentences to be built-up using truth functional connectives and quantifiers. A quantified sentence is constructed by universally or existentially generalizing on a name, i.e., by replacing all occurrences of a name by a new variable v and prefixing the sentence with~ v or~ x. For example, we have (Vv)(vx)(3y}(L x y): EVERYONE LOVES SOMEONE (OR OTHER); (iy)('4u)(ux){L x y): EVERYONE LOVES SOMEONE (IN PARTICULAR); (iy)(vy) (Vx ){ [ x y): Sm1EONE IS LOVED BY EVERYONE. Note that the most natural reading for EVERYONE LOVES SOMEONE seems to be the one which does not require generalizing on names inside the predicate; the alternative reading is more naturally expressed by SOMEONE IS LOVED BY EVERYONE, which again does not require gener­ alizing on predicate names. This jibes with our general view that names which are not centers are not taken as seriously as those which are. 3. Inference: We often speak of the "logical form" of a sentence as if it is unique. But we all know that the task of testing English argu­ ments for validity can be considerably simplified if we chose the "right" representation. The trick is to expose only as much structure as is needed to see that the argument is valid: the less structure needed, the easier the inference. Predicates do have structure, but it can be provisionally masked and uncovered later only when necessary. Not all unravellings of the predicate are equally difficult. A major feature of the CL is that we ignore entities that are not centered. Derivations are trees; each node follows from its predecessor or predecessors by one of the rules. The most important feature is that the means of introducing sentences with new centers is restricted. The-centers of the premises can be thought of as the initial set of centered entities (SCE). A new entity can be introduced 1nto SCE by making it the center of a sentence and there are only two ways in which this can be done. One is to use the change of center rule, which allows us to change a sentence into one which "says the same thing" but singles out different individual as the center. The other is the introduction of a temporary assumption with an ent1ty that was not previously in SCE. The number of applications of change of centers and the number of individuals brought into SCE are measures of the difficulty of a derivation. The rules are divided into four groups. l:These rules allow the usual kinds of inferences~ e.g ., A"-B from premises A and B. Most rules in this group do not need the structure of predicates. Constraints on quantification: (a) universal instantiation will be allowed onry-with names for entities in SCE, i.e., we can infer {mx) (L j x) from ~y)(mx)(L y x) and an additional premise of the form (jy)(P ... y . .. ). ~Existential generalization will be allowed only on names for entities in SCE. Thus, we can infer {iy){mx){L j x) from {mx){L j x) if j·SCE. Of course, we can always infer {~x){L j x) from {mx)(L j x) since the entity named m is centered. 2. These rules concern jnferences which turn on the structure of the predicate, but which do not require us to recognize any names occurring in the predicate, e.9 . , we can derive {jx){Px)l' {jx){Qk) from {jx){PxAQk). Hith these rules, we can bring out the structure of the predicate so that the sentential rules can be applied to it. 3. This group contains only one rule, the change of center rule, which allows us to infer, e .g., {jx){Gxma)which attributes a property to John {say, the property of giving Mary {the boo~ "Artificial Intelligence") from another sentence {ax){Gjmx) which attributes a property to "Artificial Intelligence" (say, the property of being 9iven by John to Mary). 4. Finally, we have rules for changing bound variables and "instantiating" centers. In the usual formal system, changing bound variables requires an application of instantiation followed by another of generalization . In our system, these rules are restricted so that the strategy might re­ quire an additional application of change of center . Since the bound variable is an accidental feature of the representation, we feel that there should be rules which allow the bou~d variables to be changed directly. Center instantiation is needed to get the equivalence between (ax)(Bxxd~ and (ax)(Bxad) . 4. A Fur·mal System (tentative version): The language of Centered Logic (CL) is defined as follows, given a formulation of first order predicate calculus {FOPC). A predicate of CL is a formula of FOPC containing at most one free variable. An atomic sentence of CL is of the form (ax)(P) where P is a predicate containing no free variable other than x and a is an individual constant. A s~utence of CL is a member of the smallest set X containing the atomic sentences and closed under the following conditions: (i) if A and Bare members of X, then so are (AAB), {AVB), and (A+B). (ii) If A and B are members of X and Aa is a result of substituting x fgr all occ~rre~ces of a in A, then, A, (Vx)(Ax), (ix)(Ax) are all members of X. A pse~do-sentence of CL is either a sentence of CL or the result of substituting an individual variable for an individual constant in a sentence of CL. Some of the metamathemat­ ical variables we use are: A, B, C, D, ... for pseudo-sentences of CL; P, Q, R, . . . for predicates of CL; a, b, c, ... for individual constants of FOPC ; u, v, w, x, y, z, ... for variables of FOPC. The translations between CL and FOPC are obvious. (Note: CL could have been formulated as a kind of A-calculus in which A operators are used to form predicates from formulas subject to two restrictions: (i) the predicates formed are monadic; we do not have predicates of the form Ax 1 x 2 ... xnA. (ii) The A operators cannot be nestea.) Inference Rules: The notation is that or Prawitz, Natural Deduction. Double lines indicate that the rule applies in either direction. ![Image](https://ijcai.org/proceedings/1979/fulltext/95/image_000000_ba76a766e0148690f5eb92df8dd6e223157fe4a32d6b9cc8ae9f884fa0c8431e.png) Restrictions: In the first rule in (1.5), a must occur in any assumption on which A depends. In the second (1.6) rule, a must not occur in ~~~~A~~c~;r~~c!n~fa~s~:~~~~~ ~~c:~ic~~~he ## 2. Pr~dicate Decomposition | 2·:1 (o.:~t) (PI'Q.) lA:~t) CP) "c.~Scan | ~.t. C«X)(PV'I) (o.x)(. P) v (~ (') | |--------------------------------------------------------|---------------------------------------| | ~ · ?. (o..x)(P+-) (o.x) ( r) -t(o.x5CQ) | 2 ·4 {O..X) (., f') ., ( o.:~t) ( P5 | | l·5 (e.x)(vy) (P) (Y.') (cr..x;> (r) ~tovltltcl X ~-'. | 1·' (a.x.)(i!I)(P) (I j) < •x) t: PJ | ## 3. Change of Topics ## 'l·i (.~)(I') tbx) (1': :) ## 4. Bound Variables ## <4· i t'l:t) C A) (.V!j){A~') 4·2 ~x)(A) t~:.) ( ,.~) 4·) {~)CA) (a'J)("~) ""'-ere lt. 1 ,·, t-'-t t'UI&.It. ·f "l.f'l&cm, ·"t. · ., MOre .,.ft 0 CC I&.Wt~U of Jf. i11 II. 1.~ ct.. · ## 5. Sample Derivations: (la) Ever)one at the reception was thanked (T) by John (j . Mary (M) was at the reception (R). (therefore) Mary was thanked by John. ## ty'IA) (14%,) (.l~\_,Tj:c) (."'x.) (.lihc.) ## ~~) ( l:~t. \_. "Tj:c) ~"-) (.lhc.) .. (IIIZ.)(Tj:C) ('M:C)(lx) (.'l'Mt) (.TJ:c) - (lb) John thanked everyone at the reception. ~ wasiat the reception. (therefore) John tnanked Mary. ## (j:t.){'i~)(~~-+ T:~t~) (V,) (j.lt) (. R' \_.,.-.~) < ""'") ( IZ:c) c.j ,c.) ( ~"" -+ ,. ·· ) (~"-) (i,c. ~ Tj-.) ('III~(R:c)~ (M:c)(ij~t) ~"-)(,:c) ('ri\X) (Tj:IC) l. j:IC) (1'-"~) (lb) is a more difficult inference than (la) because it requires two applications of the change of center rule (marked by double lines). Neither the inference in (la) nor in (lb) re­ quires bringing into SCE (Set of Centered Entities) a new entity which was not a center of a premise. This contrasts with the following derivation (2) which requires two new entities to be brought into SCE. The inherent difficulty of the inference in (2) below is due to this require­ ment, at least with respect to the CL. - (2) There is a house in which everyone lives (L) (therefore) EYer;Yone lives in houses. | | (b:t)(P)'* ( .. :c) ( P)-t (-.x) ( P) (\a~) { P-.f) | |-----------------------------------------------|-------------------------------------------------------------------------| | ( l.:c,)( P.) ... ( b.X.)( p) ("-") ( ,,.. p) | (IPx)(L:co.,) (.o.~)t'h){Lll!j) (;a:t)(bx.) (LX~) (lt.x) (.3%) (L.lt:S) | ## ~-311) (11:t)(IJx)(L:c,) (''I\1.)(14")GI:s)(.Lx:t) ta'S)( .. )(t.;!.') It is not difficult to prove that the rules given for CL are complete in the sense that A can be derived from rwhenever the* translat i on (from CL to FOPC) of A is classically derivable from the * translation of r. To see this, note that (i) the a-translation (fro~ FOPC to CL) of the classical natural deduction rules are all derivable from our rules, and* (ii ) A* 0 is provably equivalent to A. However, we need both the change of center and the introduction of temporary assumptions with new centers to get this result . (The former is needed to establ i sh the equivalence of A and A* 0 and the latter to show that translations of the classical quanti­ fier rules are derivable.) If premises and con­ clusions have the same center, then no change of center rules are needed. for, if a is the center of premises and conclusions, then by transl ating each classical ~ as (ax)( ~ ) and using the predi ­ cate decomposition rules, the classical der i va­ tion of the *-translation of the argument can be converted to a CL derivation without center changes. Hence, the number of center c h~nqes need never exceed the number of premises whose centers are distinct from the centers of the conclusion. (The role of center change becomes more interestin~. and more difficult to unde r­ stand, when quantification into the predicate is prohibited. As we mentioned previously, there is some reason to believe that this restriction is appropriate . ) Although a restri ction could be placed 0n the number of center changes, no such limit can be placed on the number of new entities which must be brought into SCE. The premise in Example (2) contains no individual constant at all. It is clear from the rules that from such formulas alone we can only derive equivalent formulas and tautologous consequences. Hence, the introduction of new centers in Example (2) was unavoidable. Thus, the logic resulting from a restriction on the number of centered entities is less powerful than one without, in particular, the logic with zero centered entities is less powerful than the logic with one centered individual. General questions about the number of new centers re­ quired for an inference and the decidability of the class of inferences with small number of centers remain open. ## References (a few selected ones): - [1] Brachman, R.J., "A Structural Paradigm for Representing Knowledge," Bolt Beranek and Newman, Inc., Report No. 3605, May 1978. - [2] Bobrow, D.G. and Winograd, T., "An Overview of KRL, a Knowledge Representation Language," Cognitive Science, vol. 1, No. 1, Jan. 1977. - [3] Boolos, G.S. and Jeffery, R., Computability and Loaic, Cambridge University Press, Cambri ge, 1974. - [4] Chafe, \~.L., "Givenness, Contrastiveness, Definiteness, Subjects, Topics, and Points of Views," in Subject and Topic (ed. C.N. Li), Academic Press, New York, 1976. - [5] Grosz, B., "The Representation and Use of Focus in Dialogue Understanding," Stanford Research Institute Technical ~epor!~· Menlo Park, California, 1977. - [6] Seidner, C., "The Use of Focus as a Tool for Disambiguation of Definite Noun Phrases," TINLAP 2, Urbana-Champaign, Illinois, 1978. - [7] Sga 11 , P. , Haj i cova, E., and Benecova, E., Topic, Focus, and Generative Semantics, Scriptor Verlag Gmbh, Kronberg Taunus, 1973. - [8] Prince, E., "On the Given/New Distinction," Proc. Chicago Linguistics Society, 1979. ## References 1. Brachman, R.J., "A Structural Paradigm for Representing Knowledge," Bolt Beranek and Newman, Inc., Report No. 3605, May 1978. 2. Bobrow, D.G. and Winograd, T., "An Overview of KRL, a Knowledge Representation Language," Cognitive Science, vol. 1, No. 1, Jan. 1977. 3. Boolos, G.S. and Jeffery, R., Computability and Loaic, Cambridge University Press, Cambri ge, 1974. 4. Chafe, \~.L., "Givenness, Contrastiveness, Definiteness, Subjects, Topics, and Points of Views," in Subject and Topic (ed. 5. C.N. Li), Academic Press, New York, 1976. 6. Grosz, B., "The Representation and Use of Focus in Dialogue Understanding," Stanford Research Institute Technical ~epor!~• Menlo Park, California, 1977. 7. Seidner, C., "The Use of Focus as a Tool for Disambiguation of Definite Noun Phrases," TINLAP 2, Urbana-Champaign, Illinois, 1978. 8. Sga 11 , P. , Haj i cova, E., and Benecova, E., Topic, Focus, and Generative Semantics, Scriptor Verlag Gmbh, Kronberg Taunus, 1973. 9. Prince, E., "On the Given/New Distinction," Proc. Chicago Linguistics Society, 1979.