12.3097, Review: Processing with Constraint-Logic Grammars

[LINGUIST List]

LINGUIST List:  Vol-12-3097. Sat Dec 15 2001. ISSN: 1068-4875.

Subject: 12.3097, Review: Processing with Constraint-Logic Grammars

Moderators: Anthony Aristar, Wayne State U.<aristar at linguistlist.org>
            Helen Dry, Eastern Michigan U. <hdry at linguistlist.org>
            Andrew Carnie, U. of Arizona <carnie at linguistlist.org>

Reviews (reviews at linguistlist.org):
	Simin Karimi, U. of Arizona
	Terence Langendoen, U. of Arizona

Editors (linguist at linguistlist.org):
	Karen Milligan, WSU 		Naomi Ogasawara, EMU
	Jody Huellmantel, WSU		James Yuells, WSU
	Michael Appleby, EMU		Marie Klopfenstein, WSU
	Ljuba Veselinova, Stockholm U.	Heather Taylor-Loring, EMU
	Dina Kapetangianni, EMU		Richard Harvey, EMU
	Karolina Owczarzak, EMU		Renee Galvis, WSU

Software: John Remmers, E. Michigan U. <remmers at emunix.emich.edu>
          Gayathri Sriram, E. Michigan U. <gayatri at linguistlist.org>

Home Page:  http://linguistlist.org/

The LINGUIST List is funded by Eastern Michigan University, Wayne
State University, and donations from subscribers and publishers.



Editor for this issue: Terence Langendoen <terry at linguistlist.org>
 ==========================================================================
What follows is another discussion note contributed to our Book
Discussion Forum.  We expect these discussions to be informal and
interactive; and the author of the book discussed is cordially invited
to join in.

If you are interested in leading a book discussion, look for books
announced on LINGUIST as "available for discussion."  (This means that
the publisher has sent us a review copy.)  Then contact
Simin Karimi at simin at linguistlist.org
or Terry Langendoen at terry at linguistlist.org.

Subscribe to Blackwell's LL+ at http://www.linguistlistplus.com/ and
donate 20% of your subscription to LINGUIST! You get 30% off on
Blackwells books, and free shipping and postage!


=================================Directory=================================

1)
Date:  Tue, 11 Dec 2001 13:42:58 +0200
From:  Kiril Simov <kivs at bgcict.acad.bg>
Subject:  Review of Minnen, Efficient Processing with Constraint-Logic
         Grammars Using Grammar Compilation

-------------------------------- Message 1 -------------------------------

Date:  Tue, 11 Dec 2001 13:42:58 +0200
From:  Kiril Simov <kivs at bgcict.acad.bg>
Subject:  Review of Minnen, Efficient Processing with Constraint-Logic
         Grammars Using Grammar Compilation

Minnen, Guido (2001) Efficient Processing with Constraint-Logic
Grammars Using Grammar Compilation. CSLI Publications, paperback ISBN
1-57586-306-5, viii+255pp, Stanford Monographs in Linguistics.

Petya Osenova* and Kiril Simov, Linguistic Modeling Laboratory, Central
Laboratory for Parallel Processing, Bulgarian Academy of Sciences.

*The first reviewer is also affiliated with Sofia University
"St. Kliment Ohridski"

OVERVIEW
This is a monograph based on the author's dissertation. It is intended
for computational linguists mainly, but its interdisciplinary approach
makes it useful for formal linguists and computer scientists as well.

The book focuses on the practical and theoretical problems that arise
when processing with Constraint-logic grammars. The author proposes
compilation techniques as a repairing tool for reducing the declarative
under-determination. His approach is considered as an alternative to
approaches requiring manual encoding of control information for
processing declarative grammars. The author distinguishes two kinds of
'declarative under-determination' (p. 2): (1) 'syntactic under-
determination' -- declarative under-determination resulting from the
fact that information necessary for syntactic processing is not
available; (2) 'lexical under-determination' -- declarative under-
determination that results from the absence of restricting information
when processing the lexicon. Minnen's approach is tested on an HPSG
formalism as an example of the constraint-based grammars and relies on
the interaction between bottom-up and top-down control strategies.

The contents structure of the monograph follows the division between
the two kinds of under-determination. After the two introductory
chapters (Introduction and Processing with Constraint-logic Grammars),
the contents of the book is divided into two main parts: Syntactic
Under-determination and Lexical Under-determination with the relevant
chapters. At the end of the book a Conclusion chapter is added. Five
appendices, a list of references and an Index follow the text body.
Each chapter follows a strict schema: it starts with a description of
the problem considered in it, a motivation (both linguistic and
processing), then an outline of the proposed decision of the problem is
given and the chapter ends with a summary of the related works.

The introduction explains the author's motivation for practically
oriented dealing with the topic and discusses the key words in his
work: constraint-logic grammars, declarative under-determination and
grammar compilation. The importance of the author's approach is
highlighted with respect to the modularity between grammar and control,
and grammar reversibility. There is a summary of the monograph contents
as well.

Chapter 2 is entitled "Processing with Constraint-logic Grammars". In
this chapter the formal preliminaries for the rest of the book are
defined and explained. The chapter discusses two topics: definitions of
constraint-logic grammars and processing with constraint-logic
grammars. In the first part the notion of constraint-logic grammars is
formally defined. Two subclasses of them are introduced and
interrelated: logic grammars based on first-order logic and typed
feature grammars based on typed feature logic. The two kinds of
grammars are defined in a uniform manner in order to stress the
relations between them. The author pays a special attention to the
typed feature grammars because of their novelty in comparison to the
first-order logic based grammars. He relies on several techniques and
assumptions: Hoehfeld and Smolka's (1988) investigations of the
requirements for extension of a constraint language with relations;
closed world interpretation (Gerdemann and King 1994) and Prolog
notations. Some basic concepts on generation and parsing with these
grammars are introduced. Then the author concentrates on the
implementation of the Head-driven Phrase Structure formalism using
typed feature grammars. Also a concrete system, ConTroll, is shortly
discussed along the lines of the typed feature grammars. The second
part of the chapter presents a typology of the control strategies with
respect to their interrelation: top-down, bottom up and head-driven
approaches. The author aims at techniques, which are applicable to both
processes - generation and parsing, using one and the same control
strategy. In pursuing his aim, he discusses 'reversible grammars'.
According to him, the reversibility is accomplished via two distinct
definitions for generating a grammar and parsing a grammar, both of
which are derived from the grammar by means of a transformation.

Part I "Syntactic Under-determination" consists of three chapters (3, 4
and 5 respectively). Each of them starts with a motivation section and
concludes with a related work section and a summary section.

Chapter 3 is entitled "Top-down Control and Syntactic Under-
determination". In it, the problem of syntactic  under-determination is
explored via the ratio between some linguistic phenomena (e. g.
topicalisation and empty heads), the order of the processing steps and
the head-driven control. On the basis of a small example, the author
shows how the efficiency of the processing and even the termination of
logic grammars depend on the order in which the literals of the grammar
are processed. To solve this problem, the author proposes a grammar
transformation technique, called 'literal rearrangement' and describes
its implementation in Prolog. The procedure takes as input a grammar
and a description of the instantiation of the grammar input. The result
of the procedure is a new grammar semantically equivalent to the
original one that demonstrates better performance on the input of the
specified type. Literal rearrangement procedure uses as an indicator of
the relative processing efficiency the notion of 'degree of non-
determinism', which is applied to a literal. This is a measurement of
the different instantiations of the literal with respect to its
evaluation context -- the grammar and the instantiated parts of the
literal. The procedure aims at minimization of the degree of the
literal non-determinism at each step of the grammar processing.

Chapter 4, "Top-down Control and Recursion on Structure" focuses on the
termination properties of top-down control in the light of syntactic
under-determination. As the structural recursion is often used in
lexicalist-based formalisms like HPSG, the author seeks adequate
repairing of the problematic cases. First of all, two main types of
recursion are discussed: the so-called 'peeling recursion' and
'building recursion'. The latter comprises the left recursion in
parsing and the head recursion in generation. Then the notion of
'argument sequence' is proposed. In this way it is possible to
predetermine whether a recursive procedure is guaranteed to terminate.
Four types of argument sequences are distinguished according to the
type of recursion: peeling, building, neutral and none of them. As the
problematic cases go mainly into building recursion, a transformation
scheme, called 'Building recursion reversal' (BRR) is suggested. This
mechanism is intended to transform a non-terminate grammar into its
terminate semantically equivalent grammar, more precisely -- into a
peeling argument sequence, and then the problem with the recursion is
solved.

Chapter 5 is entitled "Bottom-up Control using Magic". It preserves the
priorities about unifying control strategies for both NLP tasks --
parsing and generation, stated in the previous chapter. The author
proposes a solution to the syntactic-under-determination (such as
spurious ambiguity) from the bottom-up perspective, using magic
(templates) transformation. This transformation becomes necessary as a
restrictive filtering component to the guaranteed termination. Two
dynamic control strategies are presented and compared: semi-naive magic
control and Earley control. Then the author proposes a 'selective magic
HPSG parser' which combines the bottom-up processing and top-down
control. His suggestions are as follows: (1) the so called 'parse
types', i.e. words and phrases are better parsed bottom-up in
lexicalist-oriented formalisms; (2) non-parse types are processed using
advanced top-down control strategy (Goetz and Meurers 1997). The author
gives details concerning the implementation of the 'selective magic
HPSG parser'. It was implemented in Prolog by the author himself for
the ConTroll system and tested with a linearization grammar of German
(Hinrichs et. al. 1997). The reported results are somewhat
controversial: the module is faster in some cases but slower in others
(such as: delayed goals). The problem sources are detected and pointed
out along with the areas that need further exploration.

Part II is entitled "Lexical Under-determination". It consists of two
chapters (6 and 7). The structure follows the section types of Part I:
each chapter starts with a motivation section and concludes with a
related work section and a summary section.

Chapter 6, "Lexical Rules as Systematic Covariation in Lexical
Entries", proposes a new computational treatment of lexical rules in
HPSG. It is a well-known fact that via lexical rules the horizontal
generalizations in the lexicon are captured. Hence their processing
becomes a question of great importance, especially in lexicalized
linguistic theories as HPSG. From the two possibilities of formalizing
the lexical rules, meta-level approach (Calcagno and Pollard 1995) and
description-level approach (in which lexical rules become a part of the
theory), the author adopts the latter. He proposes an encoding of
lexical rules as systematic covariation in lexical entries. The
underlying motivation is the following: such an approach takes into
account the peculiarities of the lexical rules as well as the
exceptions to them. Last but not least, it is applied to finite-length
lists and thus the problem with the potentially infinite lexicons is
reduced.

After these theoretical considerations, the author describes the
compiler which exemplifies the proposed idea. Four compilation steps
are discussed: (1) Trivial translation of lexical rules into definite
clauses and explication of their frame (i.e. the features that have
been left unspecified by the linguist); (2) Determination of the
possible lexical rules interaction via finite-state automata (this step
eliminates the unsuccessful applications); (3) Finite-state automata
are further fine-tuned according to the word classes in the lexicon;
(4) Finite-state automata are translated into typed feature logic
definite clauses and the interaction with the lexicon is guaranteed by
indexing. A new idea about the lexicon is suggested. The covariation
lexicon is meant to include extended lexicon (lexical entries
specifying words that can or cannot undergo lexical rule application)
and lexical rule predicates. The author is aware of the limitation
areas such as spurious ambiguity and non-determinism.

Chapter 7 is entitled "Optimized Covariation Lexica" and it is
obviously inspired by the problem sources, stated in the previous
chapter. The author comes to the conclusion that lexical lookup needs
to be constrained. Hence two grammar transformations are proposed in
order to improve processing constraint propagation and unfold
transformation. As to the implementation of the tool in question, it is
implemented in Prolog by Detmar Meurers, the author and in cooperation
with Dieter Martini. The tool has been tested on lexical rules that
refer to syntactic and morphological information. Its advantage is its
speed.

CRITICAL EVALUATION
The book presents an up-to-date view on automatic transformation of
declarative logic grammars with respect to speeding-up their
performance and in some cases insuring the termination. It highlights
the role of the linguistic specifications for the efficient Natural
Language Processing.

The book is written in a clear and reader-friendly manner. It has a
consistent logical structure of the content, elaborate explanations and
references within the text body, which facilitates the process of
following up and understanding the author's ideas.

One drawback of the book concerns typography: there is missing content
of illustrative figures (for example, fig. 4.17, p. 90), there are
repetitions of whole passages (for example, p.30-31) and some other
minor typos.

REFERENCES
Calcagno, Mike and Carl Pollard (1995) Lexical Rules in HPSG: What are
they? Manuscript, Ohio State University, Columbus, Ohio, USA.

Earley, Jay (1970) An efficient Context-free Parsing Algorithm.
Communications of the Association for Computing Machinery 13(2), 55-61.

Gerdemann, Dale and Paul King (1994) The Correct and Efficient
Implementation of Appropriateness Specifications for Typed Feature
Structures. Proceedings of the 15th Conference on Computational
Linguistics, Kyoto, Japan, pp. 956- 960.

Goetz, Thilo and Detmar Meurers (1997) The ConTroll System as Large
Grammar Development Platform. Proceedings of the Association of
Computational Linguistics post-conference workshop on Computational
Environments for Grammar and Linguistic Engineering, Madrid, Spain.

Hinrichs, Erhard, Detmar Meurers, Frank Richter, Manfred Sailer and
Heike Winhart (1997) Ein HPSG-fragment des Deutschen, Teil 1: Theorie.
technical report SFB 340 95. University of Tuebingen, Germany.

Hoehfeld, Markus and Gert Smolka (1988) Definite relations over
Constraint Languages. Tecnical Report 53. IBM, Germany.

ABOUT THE REVIEWERS
Petya Osenova and Kiril Simov, are currently involved in the
BulTreeBank Project (HPSG-based Syntactic Tree Bank of Bulgarian): a
joint project between Linguistic Modeling Department, Bulgarian Academy
of Sciences and Seminar fur Sprachwissenschaft (SfS), Eberhard-Karls-
Universitat,Tuebingen, Germany.

Petya Osenova is researcher in Linguistics. She is assistant professor
in syntax at the Sofia University as well. Her scientific interests are
mainly in formal and corpus linguistics.

Kiril Simov is researcher in Computer Science. His scientific interests
are in computational Linguistics, constraint-based formalisms and
logics, knowledge representation and Ontologies.


---------------------------------------------------------------------------

If you buy this book please tell the publisher or author
that you saw it reviewed on the LINGUIST list.

---------------------------------------------------------------------------
LINGUIST List: Vol-12-3097