文档介绍：An NCE Context-sensitive Graph Grammar and
its Application to Visual Languages
Yoshihiro Adachi†, Yuichi Nakajima†, and Suguru Kobayashi‡
†Department of Information puter Sciences, Toyo University
2100, Kujirai, Kawagoe, Saitama, 3508585, Japan
Email:******@, ******@
‡NEC Software Ltd.
1-18-6, Shinkiba, Koutou-ku, Tokyo, 1368608, Japan
Email:kobayashi-******@
Abstract al. [10] have developed a reserved graph grammar
based on Rekers et al.’s layered graph grammar. The
In this paper we describe a neighborhood-controlled
reserved graph grammar is also context-sensitive, and
embedding (NCE) context-sensitive graph grammar.
its parsing algorithm is of polynomial plex-
The grammar can be flexibly used to formalize the
ity in most cases. As these studies have indicated,
graph-syntax rules of a wide range of visual lan-
parsing with respect to a given graph grammar is im-
guages. We discuss parsability, that is, whether or
portant puterized visual-language processing
not a derivation can be found for a given graph by
on the basis of that graph grammar.
the reverse application of the grammar’s productions.
Adachi et al. [11] have defined a context-sensitive
We also discuss position of the production
graph grammar with neighborhood controlled embed-
copies. position of the production copies is
ding (