Synthesizing transformations on hierarchically structured data
Abstract
This paper presents a new approach for synthesizing transformations on tree-structured data, such as Unix directories and XML documents. We consider a general abstraction for such data, called hierarchical data trees (HDTs) and present a novel example-driven synthesis algorithm for HDT transformations. Our central insight is to reduce the problem of synthesizing tree transformers to the synthesis of list transformations that are applied to the paths of the tree. The synthesis problem over lists is solved using a new algorithm that combines SMT solving and decision tree learning. We have implemented our technique in a system called HADES and show that HADES can automatically synthesize a variety of interesting transformations collected from online forums.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Jun 02, 2016
- Source ID
- 10.1145/2980983.2908088
Entities
People
- Christian Klinger
- Işıl Dillig
- Navid Yaghmazadeh
- Swarat Chaudhuri
Organizations
- Air Force Research Laboratory
- National Science Foundation
- Rice University
- University of Freiburg
- University of Texas at Austin