Search: id:"swepub:oai:DiVA.org:umu-216195" >
Transduction from t...
Transduction from trees to graphs through folding
-
- Berglund, Martin, 1981- (author)
- Umeå universitet,Institutionen för datavetenskap
-
- Björklund, Henrik (author)
- Umeå universitet,Institutionen för datavetenskap
-
- Björklund, Johanna, 1961- (author)
- Umeå universitet,Institutionen för datavetenskap
-
show more...
-
- Boiret, Adrien (author)
- Laboratoire d'Informatique d'Orléans & INSA CVL, France
-
show less...
-
(creator_code:org_t)
- Elsevier, 2023
- 2023
- English.
-
In: Information and Computation. - : Elsevier. - 0890-5401 .- 1090-2651. ; 295
- Related links:
-
https://doi.org/10.1...
-
show more...
-
https://umu.diva-por... (primary) (Raw object)
-
https://urn.kb.se/re...
-
https://doi.org/10.1...
-
show less...
Abstract
Subject headings
Close
- We introduce a fold operation that realises a tree-to-graph transduction by merging selected nodes in the input tree to form a possibly cyclic output graph. The work is motivated by the increasing use of graph-based representations in semantic parsing. We show that a suitable class of graphs languages can be generated by applying the fold operation to regular unranked tree languages. We investigate two versions of the fold operation, one that preserves a depth-first ordering between the edges, and one that does not. Finally, we demonstrate that the time complexity for the associated non-uniform membership problem is solvable in polynomial time for the order-preserving version, and NP-complete for the order-cancelling one.
Subject headings
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Keyword
- Graphs
- Semantic representations
- Tranducers
- Trees
Publication and Content Type
- ref (subject category)
- art (subject category)
Find in a library
To the university's database