The Recognition Capacity of Local Syntactic Constraints

THE RECOGNITION CAPACITY OF LOCAL SYNTACTIC CONSTRAINTS Mori Rimon' Jacky Herz ~ The Computer Science Department The Hebrew University of Jerusalem, Giv'at Ram, Jerusalem 91904, ISRAEL E-mail: rimon@hujics.BITNET Abstract Givcn a grammar for a language, it is possible to create finite state mechanisms that approximate its recognition capacity. These simple automata consider only short context information~ drawn from local syntactic constraints which the grammar hnposes. While it is short of providing the strong generative capacity of the grammar, such an approximation is useful for removing most word tagging ambiguities, identifying many cases of iU-fonncd input, and assisting efficiently in othcr natural language processing tasks. Our basic approach to the acquisition and usage of local syntactic constraints was presented clse- whcre; in this papcr we present some formal and empiric-,d results pertaining to properties of the approximating automata. 1. Introduction Parsing is a process by which an input sentence is not only recognized as belonging to the lan- guage, but is also assigned a structure. As [l]erwick/Wcinbcrg 84] commcnt, recognition per se (i.e. a weak generative capacity analysis) is not of much value for a theory of language understanding, but it can be useful "as a diag- nostic". We claim that if an cfficient recognition procedure is availat~le, it can be tnost valuable as a prc-parsing reducer of lcxical ambiguity (espe- cially, as [Milne 86] points out, for detcnninistic parsers), and cvcn more useful in applications where full parsing is not absolutely required - e.g. identification of iU-formed inputs in a text critique program. Still weaker than recognition procedures are 'methods which approximate the recognition capacity. This is the kind of methods that we discuss in this paper. More specifically, we analyze the recognition capacity of automata based on local (short context) considerations. In [Herz/Rimon 91] we prescnted our approach to the acquisition and usage of local syntactic constraints, focusing on its use for reduction of word-level ambiguity. After briefly reviewing this method in section 2 below, we examine in more detail various char- acteristics of the approximating automata, and suggest several applications. 2. Background: Local Syntactic Constraints Let S = Wi,..., W• be a sentence of length N, {Wi} being the words composing the sentence. And let ti ..... t• be a tag image corresponding to the sentence S, {ti} belonging to the tag set T - the set of word-class tags used as terminal symbols in a given grammar G. Typically, M=N, but in a more general environment we allow M > N . This is useful when dealing with languages where morphology allows cliticization, concatenation of conjunctions, prepositions, Or determiners to a verb or a noun, etc.; in gram- mars for l lebrew, for example, it is convenient J M. Rimon's main atfiliafion is the IBM Scientific Center, i laifa, Israel, E-mail: rimon@haifasc3.iinusl.ibm.com 2 j. I Icrz was partly supported by the I.eihniz ('enter for R.esearch in Computer Science, the ! lebrew University, and by the Rau foundation of the Open University. 155 - to assume that a …

Content truncated to 500 words