Item Details

Print View

Neighborhood Expansion Grammars

Pfaltz, John
Format
Report
Author
Pfaltz, John
Abstract
Phrase structure grammars, in which non-terminal symbols on the left side of a production can be rewritten by the string on the right side, together with their Chomsky hierarch classification, are familiar to computer scientists. But, these gramamars are most effective only to generate, and parse, strings. In this report, we introduce a new kind of grmmar in which the right side of the production is simply appended to the intermediate structure in such a way that the left side becomes its "neighborhood" in the new structure. This permits the grammatical definition of many different kinds of "n-dimensional" discrete structures. Several examples are given. Moreover, these grammars yield a formal theory grounded in antimatroid closure spaces. For example, we show that restricted neighborhood expansion grammars capture the essence of finite state and context free phrase structure grammars.
Language
English
Date Received
2012-10-29
Published
University of Virginia, Department of Computer Science, 1999
Published Date
1999
Rights
All rights reserved (no additional license for public reuse)
Collection
Libra Open Repository

Availability

Access Online