16.6.2 Other Extensions to Unification

There are many other extensions to unification besides typing, including path equations (Moshier, 1988; Carpenter, 1992; Carpenter and Penn, 1994), negation (Johnson, 1988, 1990), set-valued features (Pollard and Moshier, 1990), and disjunction (Kay, 1979; Kasper and Rounds, 1986). In some unification systems these operations are incorporated into feature structures. Kasper and Rounds (1986) and others, by contrast, implement them in a separate metalanguage which is used to describe feature structures. This idea derives from the work of Pereira and Shieber (1984), and even earlier work by Kaplan and Bresnan (1982), all of whom distinguished between a metalanguage for describing feature structures and the actual feature structures themselves. The descriptions may thus use negation and disjunction to describe a set of feature structures (i.e., a certain feature must not contain a certain value, or may contain any of a set of values) but an actual instance of

a feature structure that meets the description would not have negated or disjoint values.

The unification grammars as described so far have no mechanism for disambiguation. Much recent work in unification grammars has focused on this disambiguation problem, particular via the use of probabilistic augmentations. See the History section for important references.

16.7 SUMMARY

This chapter introduced feature structures and the unification operation which is used to combine them.

• A feature structure is a set of features-value pairs, where features are un-analyzable atomic symbols drawn from some finite set, and values are either atomic symbols or feature structures. They are represented either as attribute-value matrices (AVMs) or as directed acyclic graphs (DAGs), where features are directed labeled edges and feature values are nodes in the graph.

• Unification is the operation for both combining information (merging the information content of two feature structures) and comparing information (rejecting the merger of incompatible features).

• A phrase-structure rule can be augmented with feature structures, and with feature constraints expressing relations among the feature structures of the constituents of the rule. Subcategorization constraints can be represented as feature structures on head verbs (or other predicates). The elements which are subcategorized for by a verb may appear in the verb phrase or may be realized apart from the verb, as a long-distance dependency.

• Feature structures can be typed. The resulting typed feature structures place constraints on which type of values a given feature can take, and can also be organized into a type hierarchy to capture generalizations across types.

BIBLIOGRAPHICAL AND HISTORICAL NOTES

The use of features in linguistic theory comes originally from phonology. Anderson (1985) credits Jakobson (1939) with being the first to use features (called distinctive features) as an ontological type in a theory, drawing on previous uses

of features by Trubetskoi (1939) and others. The semantic use of features followed soon after; see Ch. 19 for the history of componential analysis in semantics. Features in syntax were well established by the 1950s and were popularized by Chomsky (1965).

The unification operation in linguistics was developed independently by Kay (1979) (feature structure unification) and Colmerauer (1970, 1975) (term unification) (see page ??). Both were working in machine translation and looking for a formalism for combining linguistic information which would be reversible. Colmerauer's original Q-system was a bottom-up parser based on a series of rewrite rules which contained logical variables, designed for a English to French machine translation system. The rewrite rules were reversible to allow them to work for both parsing and generation. Colmerauer, Fernand Didier, Robert Pasero, Philippe Roussel, and Jean Trudel designed the Prolog language based on extended Q-systems to full unification based on the resolution principle of Robinson (1965), and implemented a French analyzer based on it (Colmerauer and Roussel, 1996). The modern use of Prolog and term unification for natural language via Definite Clause Grammars was based on Colmerauer's (1975) metamorphosis grammars, and was developed and named by Pereira and Warren (1980). Meanwhile Martin Kay and Ron Kaplan had been working with Augmented Transition Network (ATN) grammars. An ATN is a Recursive Transition Network (RTN) in which the nodes are augmented with feature registers. In an ATN analysis of a passive, the first NP would be assigned to the subject register, then when the passive verb was encountered, the value would be moved into the object register. In order to make this process reversible, they restricted assignments to registers so that certain registers could only be filled once, that is, couldn't be overwritten once written. They thus moved toward the concepts of logical variables without realizing it. Kay's original unification algorithm was designed for feature structures rather than terms (Kay, 1979). The integration of unification into an Earley-style approach given in Section 16.5 is based on Shieber (1985).

See Shieber (1986) for a clear introduction to unification, and Knight (1989) for a multidisciplinary survey of unification.

Inheritance and appropriateness conditions were first proposed for linguistic knowledge by Bobrow and Webber (1980) in the context of an extension of the KL-ONE knowledge representation system (Brachman and Schmolze, 1985). Simple inheritance without appropriateness conditions was taken up by number of researchers; early users include Jacobs (1985, 1987). Ait-Kaci (1984) borrowed the notion of inheritance in unification from the logic programming community. Typing of feature structures, including both inheritance and appropriateness conditions, was independently proposed by Calder (1987), Pollard and Sag (1987), and Elhadad (1990). Typed feature structures were formalized by King (1989).

and Carpenter (1992). There is an extensive literature on the use of type hierarchies in linguistics, particularly for capturing lexical generalizations; besides the papers previously discussed, the interested reader should consult Evans and Gazdar (1996) for a description of the DATR language, designed for defining inheritance networks for linguistic knowledge representation, Fraser and Hudson (1992) for the use of inheritance in a dependency grammar, and Daelmans et al. (1992) for a general overview. Formalisms and systems for the implementation of constraint-based grammars via typed feature structures include the PAGE system using the TDL language (Krieger and Schäfer, 1994), ALE (Carpenter and Penn, 1994), ConTroll (Götz et al., 1997) and LKB (Copestake, 2002).

Efficiency issues in unification parsing are discussed by Kiefer et al. (1999a), Malouf et al. (2000), and Munteanu and Penn (2004).

Grammatical theories based on unification include Lexical Functional Grammar (LFG) (Bresnan, 1982), Head-Driven Phrase Structure Grammar (HPSG) (Pollard and Sag, 1987, 1994), Construction Grammar (Kay and Fillmore, 1999), and Unification Categorical Grammar (Uszkoreit, 1986).

Much recent computational work on unification grammars has focused on probabilistic augmentations for disambiguation. Key relevant papers include Abney (1997), Goodman (1997), Johnson et al. (1999), Riezler et al. (2000), Geman and Johnson (2002), Riezler et al. (2002, 2003), Kaplan et al. (2004), Miyao and Tsujii (2005), Toutanova et al. (2005), Ninomiya et al. (2006) and Blunsom and Baldwin (2006).

EXERCISES

16.1 Draw the DAGs corresponding to the AVMs given in Examples 16.1–16.2.

16.2 Consider the following BERP examples, focusing on their use of pronouns.

I want to spend lots of money.

Tell me about Chez-Panisse.

I'd like to take her to dinner.

She doesn't like Italian.

Assuming that these pronouns all belong to the category Pro, write lexical and grammatical entries with unification constraints that block the following examples.

$ ^{*} $Me want to spend lots of money.

$ ^{*} $Tell I about Chez-Panisse.

$ ^{*} $I would like to take she to dinner.

$ ^{*} $Her doesn't like Italian.

16.3 Draw a picture of the subsumption semilattice corresponding to the feature structures in Examples 16.3 to 16.7. Be sure to include the most general feature structure [].

16.4 Consider the following examples

The sheep are baaaang.

The sheep is baaaang.

Create appropriate lexical entries for the words the, sheep, and baaaang. Show that your entries permit the correct assignment of a value to the NUMBER feature for the subjects of these examples, as well as their various parts.

16.5 Create feature structures expressing the different SUBCAT frames for while and during shown on page 21.

16.6 Alter the pseudocode shown in Figure 16.11 so that it performs the more radical kind of unification-based parsing described on page 37.

16.7 Consider the following problematic grammar suggested by Shieber (1985).

$$ \begin{aligned}&S\rightarrow T\\&\quad\langle T F\rangle=\mathbf{a}\\&T_{1}\rightarrow T_{2}A\\&\quad\langle T_{1}F\rangle=\langle T_{2}F F\rangle\\&S\rightarrow A\\&A\rightarrow a\end{aligned} $$

Show the first S state entered into the chart using your modified PREDICTOR from the previous exercise, then describe any problematic behavior displayed by PREDICTOR on subsequent iterations. Discuss the cause of the problem and how in might be remedied.

16.8 Using the list approach to representing a verb's subcategorization frame, show how a grammar could handle any number of verb subcategorization frames with only the following two VP rules. More specifically, show the constraints that would have to be added to these rules to make this work.

$$ VP\to Verb $$

$$ VP\to VP X $$

The solution to this problem involves thinking about a recursive walk down a verb's subcategorization frame. This is a hard problem; you might consult Shieber (1986) if you get stuck.

16.9 Page 43 showed how to use typed feature structures to represent constituency. Use that notation to represent rules 16.12, 16.13, and 16.14 shown on page 15.

Abney, S. P. (1997). Stochastic attribute-value grammars. Computational Linguistics, 23(4), 597–618.

Ait-Kaci, H. (1984). A Lattice-Theoretic Approach to Computation Based on a Calculus of Partially Ordered Types. Ph.D. thesis, University of Pennsylvania.

Anderson, S. R. (1985). Phonology in the Twentieth Century. Cambridge University Press.

Baker, C. F., Fillmore, C. J., and Lowe, J. B. (1998). The Berkeley FrameNet project. In COLING/ACL-98, pp. 86–90.

Blunsom, P. and Baldwin, T. (2006). Multilingual deep lexical acquisition for hpsgs via supertagging. In EMNLP 2006.

Bobrow, R. J. and Webber, B. L. (1980). Knowledge representation for syntactic/semantic processing. In AAAI-80, Stanford, CA, pp. 316–323. Morgan Kaufmann.

Brachman, R. J. and Schmolze, J. G. (1985). An overview of the KL-ONE knowledge representation system. Cognitive Science, 9(2), 171–216.

Bresnan, J. (Ed.). (1982). The Mental Representation of Grammatical Relations. MIT Press.

Calder, J. (1987). Typed unification for natural language processing. In Kahn, G., MacQueen, D., and Plotkin, G. (Eds.), Categories, Polymorphism, and Unification. Centre for Cognitive Science, University of Edinburgh, Edinburgh, Scotland†.

Carpenter, B. (1991). The generative power of categorical grammars and head-driven phrase structure grammars with lexical rules. Computational Linguistics, 17(3), 301–313.

Carpenter, B. (1992). The Logic of Typed Feature Structures. Cambridge University Press.

Carpenter, B. and Penn, G. (1994). The Attribute Logic Engine Users's Guide Version 2.0.1. Tech. rep., Carnegie Mellon University.

Chomsky, N. (1965). Aspects of the Theory of Syntax. MIT Press.

Colmerauer, A. (1970). Les systèmes-q ou un formalisme pour analyser et synthétiser des phrase sur ordinateur. Internal publication 43, Département d'informatique de l'Université de Montréal†.

Colmerauer, A. (1975). Les grammaires de métamorphose GIA. Internal publication, Groupe Intelligence artificielle, Faculté des Sciences de Luminy, Université Aix-Marseille II, France, Nov 1975. English version, Metamorphosis grammars. In L. Bolc, (Ed.), Natural Language Communication with Computers, Lecture Notes in

Computer Science 63, Springer Verlag, Berlin, 1978, pp.133–189.

Colmerauer, A. and Roussel, P. (1996). The birth of Prolog. In Bergin Jr., T. J. and Gibson, Jr., R. G. (Eds.), History of Programming Languages – II, pp. 331–352. ACM Press/Addison-Wesley, New York.

Copestake, A. (2002). Implementing Typed Feature Structure Grammars. CSLI, Stanford, CA.

Daelemans, W., Smedt, K. D., and Gazdar, G. (1992). Inheritance in natural language processing. Computational Linguistics, 18(2), 205–218.

de Tocqueville, A. (1840). Democracy in America. Doubleday, New York. The 1966 translation by George Lawrence.

Elhadad, M. (1990). Types in functional unification grammars. In Proceedings of the 28th ACL, Pittsburgh, PA, pp. 157–164. ACL.

Evans, R. and Gazdar, G. (1996). DATR: A language for lexical knowledge representation. Computational Linguistics, 22(2), 167–216.

Fraser, N. M. and Hudson, R. A. (1992). Inheritance in word grammar. Computational Linguistics, 18(2), 133–158.

Gazdar, G., Klein, E., Pullum, G. K., and Sag, I. A. (1985). Generalized Phrase Structure Grammar. Basil Blackwell, Oxford.

Gazdar, G., Pullum, G. K., Carpenter, B., Klein, E., Hukari, T. E., and Levine, R. D. (1988). Category structures. Computational Linguistics, 14(1), 1–19.

Geman, S. and Johnson, M. (2002). Dynamic programming for parsing and estimation of stochastic unification-based grammars.. In ACL-02, pp. 279–286.

Goodman, J. (1997). Probabilistic feature grammars. In Proceedings of the International Workshop on Parsing Technology.

Götz, T., Meurers, W. D., and Gerdemann, D. (1997). The Controll manual. Tech. rep., Seminar für Sprachwissenschaft, Universität Tübingen.

Jackendoff, R. (1975). Morphological and semantic regularities in the lexicon. Language, 51(3), 639–671.

Jacobs, P. (1985). A Knowledge-Based Approach to Language Generation. Ph.D. thesis, University of California, Berkeley, CA. Available as University of California at Berkeley Computer Science Division Tech. rep. #86/254.

Jacobs, P. (1987). Knowledge-based natural language generation. Artificial Intelligence, 33, 325–378.

Jakobson, R. (1939). Observations sur le classement phonologique des consonnes. In Blancquaert, E. and Pée, W. (Eds.), Proceedings of the Third International Congress of Phonetic Sciences, Ghent, pp. 34–41.

Johnson, C. (1999). Syntactic and semantic principles of FrameNet annotation, version 1. Tech. rep. TR-99-018, ICSI, Berkeley, CA.

Johnson, M. (1988). Attribute-Value Logic and the Theory of Grammar. CSLI Lecture Notes. Chicago University Press, Chicago.

Johnson, M. (1990). Expressing disjunctive and negative feature constraints with classical first-order logic. In Proceedings of the 28th ACL, Pittsburgh, PA, pp. 173–179. ACL.

Johnson, M., Geman, S., Canon, S., Chi, Z., and Riezler, S. (1999). Estimators for stochastic “unification-based” grammars. In ACL-99, pp. 535–541.

Jurafsky, D. (1992). An On-line Computational Model of Human Sentence Interpretation: A Theory of the Representation and Use of Linguistic Knowledge. Ph.D. thesis, University of California, Berkeley, CA. Available as University of California at Berkeley Computer Science Division Tech. rep. #92/676.

Kaplan, R. M., Riezler, S., King, T. H., Maxwell, J. T., Vasserman, A., and Crouch, R. (2004). Speed and accuracy in shallow and deep stochastic parsing. In HLTIAACL-04.

Kaplan, R. M. (1987). Three seductions of computational psycholinguistics. In Whitelock, P., Wood, M. M., Somers, H. L., Johnson, R., and Bennett, P. (Eds.), Linguistic Theory and Computer Applications, pp. 149–188. Academic Press, London.

Kaplan, R. M. and Bresnan, J. (1982). Lexical-functional grammar: A formal system for grammatical representation. In Bresnan, J. (Ed.), The Mental Representation of Grammatical Relations, pp. 173–281. MIT Press.

Karttunen, L. and Kay, M. (1985). Structure sharing with binary trees. In ACL-85, Chicago, pp. 133–136. ACL.

Kasper, R. T. and Rounds, W. C. (1986). A logical semantics for feature structures. In ACL-86, New York, pp. 257–266. ACL.

Kay, M. (1979). Functional grammar. In BLS-79, Berkeley, CA, pp. 142–158.

Kay, M. (1984). Functional unification grammar: A formalism for machine translation. In COLING-84, Stanford, CA, pp. 75–78.

Kay, M. (1985). Parsing in functional unification grammar. In Dowty, D. R., Karttunen, L., and Zwicky, A. (Eds.), Natural Language Parsing, pp. 251–278. Cambridge University Press.

Kay, P. and Fillmore, C. J. (1999). Grammatical constructions and linguistic generalizations: The What's X Doing Y? construction. Language, 75(1), 1–33.

Kiefer, B., Krieger, H. U., Carroll, J., and Malouf, R. (1999a). A bag of useful techniques for efficient and robust parsing. In ACL-99, pp. 535–541.

Kiefer, B., Krieger, H.-U., Carroll, J., and Malouf, R. (1999b). A bag of useful techniques for efficient and robust parsing. In ACL-99, College Park, MD, pp. 473–480.

King, P. (1989). A Logical Formalism for Head-Driven Phrase Structure Grammar. Ph.D. thesis, University of Manchester†. Cited in Carpenter (1992).

Knight, K. (1989). Unification: A multidisciplinary survey. ACM Computing Surveys, 21(1), 93–124.

Kogure, K. (1990). Strategic lazy incremental copy graph unification. In COLING-90, Helsinki, pp. 223–228.

Krieger, H.-U. and Nerbonne, J. (1993). Feature-based inheritance networks for computational lexicons. In Briscoe, T., de Paiva, V., and Copestake, A. (Eds.), Inheritance, Defaults, and the Lexicon, pp. 90–136. Cambridge University Press.

Krieger, H.-U. and Schäfer, U. (1994). TDL — A type description language for HPSG. Part 1: Overview. Tech. rep. RR-94-37, DFKI, Saarbrücken.

Lascarides, A. and Copestake, A. (1997). Default representation in constraint-based frameworks. Computational Linguistics, 25(1), 55–106.

Macleod, C., Grishman, R., and Meyers, A. (1998). COMLEX Syntax Reference Manual Version 3.0. Linguistic Data Consortium.

Malouf, R., Carrol, J., and Copestake, A. (2000). Efficient feature structure operations without compilation. Natural Language Engineering, 6(1).

Meurers, W. D. and Minnen, G. (1997). A computational treatment of lexical rules in HPSG as covariation in lexical entries. Computational Linguistics, 23(4), 543–568.

Miyao, Y. and Tsujii, J. (2005). Probabilistic disambiguation models for wide-coverage hpsg parsing. In ACL-05, pp. 83–90.

Moshier, M. A. (1988). Extensions to Unification Grammar for the Description of Programming Languages. Ph.D. thesis, University of Michigan, Ann Arbor, MI.

Munteanu, C. and Penn, G. (2004). Optimizing typed feature structure grammar parsing through non-statistical indexing. In ACL-04, Barcelona, Spain, pp. 223–230.

Ninomiya, T., Tsuruoka, Y., Miyao, Y., Taura, K., and Tsujii, J. (2006). Fast and scalable hpsg parsing. Traitement automatique des langues (TAL), 46(2).

Penn, G. and Munteanu, C. (2003). A tabulation-based parsing method that reduces copying. In Proceedings of the 41st Annual Meeting of the ACL, Sapporo, Japan.

Pereira, F. C. N. (1985). A structure-sharing representation for unification-based grammar formalisms. In ACL-85, Chicago, pp. 137–144.

Pereira, F. C. N. and Shieber, S. M. (1984). The semantics of grammar formalisms seen as computer languages. In COLING-84, Stanford, CA, pp. 123–129.

Pereira, F. C. N. and Warren, D. H. D. (1980). Definite clause grammars for language analysis—a survey of the formalism and a comparison with augmented transition networks. Artificial Intelligence, 13(3), 231–278.

Pollard, C. and Moshier, M. A. (1990). Unifying partial descriptions of sets. In Hanson, P. P. (Ed.), Information, Language, and Cognition, pp. 285–322. University of British Columbia Press, Vancouver.

Pollard, C. and Sag, I. A. (1987). Information-Based Syn- tax and Semantics: Volume 1: Fundamentals. University of Chicago Press, Chicago.

Pollard, C. and Sag, I. A. (1994). Head-Driven Phrase Structure Grammar. University of Chicago Press, Chicago.

Reiter, R. (1980). A logic for default reasoning. Artificial Intelligence, 13, 81–132.

Riezler, S., King, T. H., Crouch, R., and Zaenen, A. (2003). Statistical sentence condensation using ambiguity packing and stochastic disambiguation methods for Lexical-Functional Grammar. In HLT-NAACL-03, Edmonton, Canada.

Riezler, S., Prescher, D., Kuhn, J., and Johnson, M. (2000). Lexicalized stochastic modeling of constraint-based grammars using log-linear measures and em training. In ACL-00, Hong Kong.

Riezler, S., King, T. H., Kaplan, R. M., Crouch, R., III, J. T. M., and Johnson, M. (2002). Parsing the wall street journal using a lexical-functional grammar and discriminative estimation techniques. In ACL-02, Philadelphia, PA.

Robinson, J. A. (1965). A machine-oriented logic based on the resolution principle. Journal of the Association for Computing Machinery, 12, 23–41.

Rounds, W. C. and Kasper, R. T. (1986). A complete logical calculus for record structures representing linguistic information. In Proceedings of the 1st Annual IEEE Symposium on Logic in Computer Science, pp. 38–43.

Sag, I. A. and Wasow, T. (Eds.). (1999). Syntactic Theory: A Formal Introduction. CSLI Publications, Stanford, CA.

Sanfilippo, A. (1993). LKB encoding of lexical knowledge. In Briscoe, T., de Paiva, V., and Copestake, A. (Eds.), Inheritance, Defaults, and the Lexicon, pp. 190–222. Cambridge University Press.

Shieber, S. M. (1985). Using restriction to extend parsing algorithms for complex-feature-based formalisms. In ACL-85, Chicago, pp. 145–152.

Shieber, S. M. (1986). An Introduction to Unification-Based Approaches to Grammar. Center for the Study of Language and Information, Stanford University, Stanford, CA.

Tomabechi, H. (1991). Quasi-destructive graph unification. In Proceedings of the 29th ACL, Berkeley, CA, pp. 315–322.

Toutanova, K., Manning, C. D., Flickinger, D., and Oepen, S. (2005). Stochastic HPSG Parse Disambiguation using the Redwoods Corpus. Research on Language & Computation, 3(1), 83–105.

Trubetskoi, N. S. (1939). Grundzüge der Phonologie, Vol. 7 of Travaux du cercle linguistique de Prague. Available in 1969 English translation by Christiane A. M. Baltaxe as Principles of Phonology, University of California Press.

Uszkoreit, H. (1986). Categorial unification grammars. In COLING-86, Bonn, pp. 187–194.

Young, M. and Rounds, W. C. (1993). A logical semantics for nonmonotonic sorts. In Proceedings of the 31st ACL, Columbus, OH, pp. 209–215. ACL.

17

REPRESENTING MEANING

ISHMAEL: Surely all this is not without meaning.

Herman Melville, Moby Dick

The approach to semantics introduced here, and elaborated on in the next four chapters, is based on the notion that the meaning of linguistic utterances can be captured in formal structures, which we will call \textit{meaning representations}. Correspondingly, the frameworks that are used to specify the syntax and semantics of these representations will be called \textit{meaning representation languages}. These meaning representations play a role analogous to that of the phonological, morphological, and syntactic representations introduced in earlier chapters.

The need for meaning representations arises when neither the raw linguistic inputs, nor any of the structures derivable from them by any of the transducers we have studied thus far, facilitate the kind of semantic processing that is desired. More specifically, what we need are representations that bridge the gap from linguistic inputs to the non-linguistic knowledge of the world needed to perform tasks involving the meaning of linguistic inputs. To illustrate this notion, consider the following everyday language tasks that require some form of semantic processing of natural language:

• Answering an essay question on an exam;

Deciding what to order at a restaurant by reading a menu:

• Learning to use a new piece of software by reading the manual;

• Realizing that you've been insulted; and

• Following a recipe.

Simply having access to the phonological, morphological, and syntactic representations that we have discussed thus far will not get us very far on accomplishing

any of these tasks. These tasks require access to representations that link the linguistic elements involved in the task to the non-linguistic knowledge of the world needed to successfully accomplish them. For example, some of the world knowledge needed to perform the above tasks would include the following:

• Answering and grading essay questions requires background knowledge about the topic of the question, the desired knowledge level of the students, and how such questions are normally answered.

Reading a menu and deciding what to order, giving advice about where to go to dinner, following a recipe, and generating new recipes all require knowledge about food, its preparation, what people like to eat and what restaurants are like.

Learning to use a piece of software by reading a manual, or giving advice about how to do the same, requires knowledge about current computers, the specific software in question, similar software applications, and knowledge about users in general.

In the representational approach explored here, we take linguistic inputs and construct meaning representations that are made up of the same kind of stuff that is used to represent this kind of everyday commonsense knowledge of the world. The process whereby such representations are created and assigned to linguistic inputs is called semantic analysis.

To make this notion a bit more concrete, consider Fig. 17.1, which shows sample meaning representations for the sentence I have a car using four representative meaning representation languages. The first row illustrates a sentence in First-Order Logic, which will be covered in detail in Section 17.4; the graph in the center illustrates a Semantic Network, which will be discussed further in Section 17.6; the third row contains a Conceptual Dependency diagram, discussed in more detail in Ch. 19, and finally a Frame-Based representation, also covered in Section 17.6.

While there are non-trivial differences among these approaches, at an abstract level they all share as a common foundation the notion that a meaning representation consists of structures composed from a set of symbols, or representational vocabulary. When appropriately arranged, these symbol structures are taken to correspond to the objects, properties of objects and relations among objects in some state of affairs being represented. In this case, all four representations make use of symbols corresponding to the speaker, a car, and relations denoting the possession of one by the other.

It is important to note that these representations can be viewed from at least two distinct perspectives in all four of these approaches: as representations of the meaning of the particular linguistic input I have a car, and as representations of

the state of affairs in some world. It is this dual perspective that allows these representations to be used to link linguistic inputs to the world and to our knowledge of it.

The structure of this part of the book parallels that of the previous parts. We will alternate discussions of the nature of meaning representations with discussions of the computational processes that can produce them. More specifically, this chapter introduces the basics of what is needed in a meaning representation, while Ch. 18 introduces a number of techniques for assigning meanings to linguistic inputs. Ch. 19 explores a range of complex representational issues related to the meanings of words. Ch. 20 then explores some robust computational methods designed to exploit these lexical representations.

Since the focus of this chapter is on some of the basic requirements for meaning representations, we will defer a number of extremely important issues to later chapters. In particular, the focus of this chapter is on representing what is sometimes called the \textit{literal} meaning of sentences. By this, we have in mind representations that are closely tied to the conventional meanings of the words that are used to create them, and that do not reflect much of the context in which they occur. The shortcomings of such representations with respect to phenomena such as idioms and metaphor will be discussed in the next two chapters, while the role of context in ascertaining the deeper meaning of sentences will be covered in Chs. 20 and 23.

There are four major parts to this chapter. Section 17.1 explores some of the key computational requirements for what we need in a meaning representation language. Section 17.2 then discusses some of the ways that languages are structured to convey meaning. Section 17.3 describes how we can more formally specify the meanings of our meaning representations. Section 17.4 then provides an introduction to First Order Logic, which has historically been the primary technique used to investigate issues in natural language semantics.

17.1 COMPUTATIONAL DESIDERATA FOR REPRESENTATIONS

We begin by considering the issue of why meaning representations are needed and what they should do for us. To focus this discussion, we will consider in more detail the task of giving advice about restaurants to tourists. In this discussion, we will assume that we have a computer system that accepts spoken language queries from tourists and constructs appropriate responses by using a knowledge base of relevant domain knowledge. A series of examples will serve to introduce some of the basic requirements that a meaning representation must fulfill, and some of the complications that inevitably arise in the process of designing such meaning representations. In each of these examples, we will examine the role that the representation of the meaning of the request must play in the process of satisfying it.