Ordered DAG Grammars and Parsing Complexity

Room FC1.004, DMat-FCUP at 15:30
Friday, 26 May, 2017 (All day)

Hyperedge Replacement Grammars are a useful and expressive formalism for generating graph languages. Unfortunately, the uniform parsing problem for such grammars is NP-hard. We investigate restrictions which allow polynomial time parsing while still retaining enough expressive power to generate interesting languages. In particular, our search for suitable restrictions is guided by applications in natural language processing.


Henrik Björklund


Umeå University, Sweden

PDF File: