Polynomial-time inverse computation for accumulative functions with multiple data traversals

Research output: Contribution to journalArticlepeer-review

9 Citations (Scopus)


The problem of inverse computation has many potential applications such as serialization/deserialization, providing support for undo, and test-case generation for software testing. In this paper, we propose an inverse computation method that always terminates for a class of functions known as parameter-linear macro tree transducers, which involve multiple data traversals and the use of accumulations. The key to our method is the observation that a function in the class can be regarded as a non-accumulative context-generating transformation without multiple data traversals. Accordingly, we demonstrate that it is easy to achieve terminating inverse computation for the class by context-wise memoization of the inverse computation results. We also show that when we use a tree automaton to express the inverse computation results, the inverse computation runs in time polynomial to the size of the original output and the textual program size.

Original languageEnglish
Pages (from-to)3-38
Number of pages36
JournalHigher-Order and Symbolic Computation
Issue number1
Publication statusPublished - 2012 Mar 1


  • Functional programming
  • Inverse computation
  • Program inversion
  • Program transformation
  • Tree automata
  • Tree transducers


Dive into the research topics of 'Polynomial-time inverse computation for accumulative functions with multiple data traversals'. Together they form a unique fingerprint.

Cite this