Parsing Directed Acyclic Graphs with Range Concatenation Grammars

Pierre Boullier and Benoît Sagot

11th International Conference on Parsing Technology (IWPT 2009)
Paris, France, 7th-9th October, 2009

---

Summary

Range Concatenation Grammars (RCGs) are a syntactic formalism which possesses many attractive properties. It is more powerful than Linear Context-Free Rewriting Systems, though this power is not reached to the detriment of efficiency since its sentences can always be parsed in polynomial time. If the input, instead of a string, is a Directed Acyclic Graph (DAG), we show that, for an important subclass, the slightly tuned standard parsing algorithm can still run in polynomial time. Nevertheless, for non-linear grammars, this polynomial parsing time cannot be guaranteed anymore.

---

START Conference Manager (V2.56.8 - Rev. 780)