Skip to content
Show report in:

UMINF 18.07

Tree-to-graph transductions with scope

High-level natural language processing requires formal languages to represent semantic information. A recent addition of this kind is abstract meaning representations. These are graphs in which nodes encode concepts and edges relations. Node-sharing is common, and cycles occur. We show that the required structures can be generated through the combination of (i) a regular tree grammar, (ii) a sequence of linear top-down tree transducers, and (iii) a fold operator that merges selected nodes. Delimiting the application of the fold operator to connected subgraphs gains expressive power, while keeping the complexity of the associated membership problem in polynomial time.


Trees, complexity, graphs, semantics, transductions


Back Edit this report
Entry responsible: Johanna Bjorklund

Page Responsible: Frank Drewes