Search: onr:"swepub:oai:DiVA.org:umu-203004" >
Tree-to-Graph Trans...
Tree-to-Graph Transductions with Scope
-
- Björklund, Johanna, 1961- (author)
- Umeå universitet,Institutionen för datavetenskap
-
(creator_code:org_t)
- 2018-08-05
- 2018
- English.
-
In: Developments in Language Theory. DLT 2018.. - Cham : Springer. - 9783319986531 - 9783319986548 ; , s. 133-144
- Related links:
-
https://urn.kb.se/re...
-
show more...
-
https://doi.org/10.1...
-
show less...
Abstract
Subject headings
Close
- 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.
Subject headings
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
- NATURVETENSKAP -- Data- och informationsvetenskap -- Språkteknologi (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Language Technology (hsv//eng)
Keyword
- Automata
- Graph languages
- Semantic representations
Publication and Content Type
- ref (subject category)
- kon (subject category)
Find in a library
To the university's database