Identification a non-deterministic operation in STCG
Loading...
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