Identification a non-deterministic operation in STCG

Loading...
Thumbnail Image
Date
1994-05
Authors
Abdul Rashid, Nur'aini
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Many grammar formalisms have been developed to fulfill the needs of Natural Language Processing towards the goal of providing formal descriptions of human languages to enhance various applic!1tions. Existing formalisms range from the simple Context-Free Grammar to very complex ones like the Definite Clause Grammar. Notational means for specifying the desired representation structures for actual language utterances are provided by grammar formalisms, but more importantly, a grammar formalism is used for defining the mapping from a text to its associated representation structure. Linguistic information coded in a grammar formalism forms a grammar, and the interpretation or implementation of a grammar to perform analysis is called a parser or analyser. A grammar formalism in principle is not much uD.like programming languages in the sense that it has its data structures and a set of underlying operations. However, the \ obvious difference is that a grammar formalism is specialised and specifically designed for writing grammRrs for natural languages, which are non-artificially designed languages, hence more vague, constantly developing, and have more expressive power than its computer language counterparts. As such, the data structures supported are usually more specific and adapted towards linguistic structures, which makes it more complex. On the other hand, to make the description effort less cumbersome as well as to avoid over generation of linguistic structures, the set of underlying operations are usually simple and in fact minimal, ranging from term unification in Definite Clause Grammar to unification in Functional Unification Grammar. One of the more recent and arguably more linguistically justified formalisms is the String-Tree Correspondence Grammar (STCG). The matching technique underlying the STCG formalism (i.e. basic operation) is identification. In this dissertation, we report on a proposed design for the implementation of identification. This involves putting forward a design for the basic data structure called woods, and to give a computationally tractable algorithm for the identification process. The -design closely follows the conceptual design of the operation as given in [Zaharin86] and [Lepage89].
Description
Keywords
Non-deterministic operation , STCG
Citation