Petri Net Grammars for Natural Language Analysis

Abstract

An approach is described to parsing and logical translation that was inspired by Lee, K.'s(1983) work on AMG(Augmented Montague Grammar) for case languages, and execution rules of Petri nets. Each grammar rule consists of a syntactic part that specifies an acceptable fragment of a parse tree, and a semantic part that specifies how the logical forms correspoding to the constituents of the fragment are to be combined to yield the logical form for the fragment in the intensional logic. The proposed model, SPNG (Semantic Petri Net Grammar) is built based on Petri nets and its parsing mechanism resembles execution rules of its underlying Petri nets. But SPNG parsing mechanism includes several constraints which block out wrong applications of rules. Also, an isomorphism exists between SPNG and AMG. SPNG has the same analytic power with Turing machine, since it is an extended Petri net with inhibitor arcs (Peterson 1981). Hence, natural languages can be parsed by SPNG sufficiently.