Some Remarks on the Geometry of Grammar

Details Some Remarks on the Geometry of Grammar Some Remarks on the Geometry of Grammar

1999-03-05

arxiv.org/abs/cs/9903007v1

Computer Science

Computation and Language

22 pages, 15 figures

Scientific paper

This paper, following (Dymetman:1998), presents an approach to grammar description and processing based on the geometry of cancellation diagrams, a concept which plays a central role in combinatorial group theory (Lyndon-Schuppe:1977). The focus here is on the geometric intuitions and on relating group-theoretical diagrams to the traditional charts associated with context-free grammars and type-0 rewriting systems. The paper is structured as follows. We begin in Section 1 by analyzing charts in terms of constructs called cells, which are a geometrical counterpart to rules. Then we move in Section 2 to a presentation of cancellation diagrams and show how they can be used computationally. In Section 3 we give a formal algebraic presentation of the concept of group computation structure, which is based on the standard notions of free group and conjugacy. We then relate in Section 4 the geometric and the algebraic views of computation by using the fundamental theorem of combinatorial group theory (Rotman:1994). In Section 5 we study in more detail the relationship between the two views on the basis of a simple grammar stated as a group computation structure. In section 6 we extend this grammar to handle non-local constructs such as relative pronouns and quantifiers. We conclude in Section 7 with some brief notes on the differences between normal submonoids and normal subgroups, group computation versus rewriting systems, and the use of group morphisms to study the computational complexity of parsing and generation.

Affiliated with

Also associated with

No associations

Rating

Some Remarks on the Geometry of Grammar does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Some Remarks on the Geometry of Grammar, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Some Remarks on the Geometry of Grammar will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-617388