Transduce: learning transduction grammars for string transformation
This addresses the challenge of learning string transformations efficiently with minimal examples, which is incremental but offers specific improvements for program synthesis tasks.
The paper tackles the problem of synthesizing string transformation programs from input-output examples by proposing Transduce, an algorithm that constructs and generalizes abstract transduction grammars, achieving a higher success rate than the state of the art.
The synthesis of string transformation programs from input-output examples utilizes various techniques, all based on an inductive bias that comprises a restricted set of basic operators to be combined. A new algorithm, Transduce, is proposed, which is founded on the construction of abstract transduction grammars and their generalization. We experimentally demonstrate that Transduce can learn positional transformations efficiently from one or two positive examples without inductive bias, achieving a success rate higher than the current state of the art.