Re: Determining the inverse function operation from a function definition

"Ron Foster" <rlfoster1@cox.net> writes:


> Hi.
> I am working on a small project to evaluate and execute unit conversion
> expressions. I started wondering whether it was possible to determine what
> the reverse conversion rules might blook like. ....


> The problem appears to lie in the domain of ( one to one ) function
> inversion or maybe equation solving.
>
> I presume that such an algorithm has been implemented a hundred or so times,
> but my research is coming up dry.
>
> I'd appreciate it if someone could point me to some relevant material.


Some relevant references (in alphabetical order):


@InProceedings{AbrGlu02:URAF,
      Author = {Abramov, Sergei M. and Gl{\"u}ck, Robert},
      Title = {Principles of inverse computation and the universal
                                  resolving algorithm},
      BookTitle = {The Essence of Computation: Complexity, Analysis,
Transformation},
      Editor = {Mogensen, Torben {\AE}. and Schmidt, David and
                                  Sudborough, I. Hal},
      Publisher = {Springer-Verlag},
      Series = LNCS # 2566,
      Pages = {269--295},
      Year = {2002}
}


@InProceedings{Dijkstra:78,
      Author = {Dijkstra, Edsger W.},
      Title = {Program inversion},
      BookTitle = {Program Construction: International Summer School},
      Editor = {Bauer, F. L. and Broy, M.},
      Location = {Marktoberdorf, Germany},
      Publisher = {Springer-Verlag},
      Series = LNCS # 69,
      Pages = {54--57},
      Year = 1978
}


@incollection{Dijkstra:book82,
      author = {Dijkstra, Edsger W.},
      title = {{EWD}671: Program Inversion},
      booktitle = {Selected Writings on Computing: {A} Personal Perspective},
      publisher = {Springer-Verlag},
      pages = {351--354},
      year = 1982
}


@inproceedings{Eppstein:IJCAI85,
      author = {Eppstein, David},
      title = {A Heuristic Approach to Program Inversion},
      booktitle = {Int.\ Joint Conference on
                                Artificial Intelligence (IJCAI-85)},
      publisher = {Morgan Kaufmann, Inc.},
      pages = {219--221},
      year = 1985,
}


@InProceedings{GlueckKawabe:04:LRinv,
      AUTHOR = {Gl{\"u}ck, Robert and Kawabe, Masahiko},
      YEAR = {2004},
      TITLE = {Derivation of deterministic inverse programs based
                                      on {LR} parsing},
      BOOKTITLE = {Functional and Logic Programming. Proceedings},
      editor = {Kameyama, Yukiyoshi and Stuckey, Peter J.},
      Location = {Nara, Japan},
      publisher = {Springer-Verlag},
      series = LNCS # 2998,
      pages = {291--306}
    }


@inbook{Gries:81:inv,
      author = {Gries, David},
      title = {The Science of Programming},
      chapter = {21 Inverting Programs},
      series = {Texts and Monographs in Computer Science},
      publisher = {Springer-Verlag},
      pages = {265--274},
      year = 1981
}


@InProceedings{Harrison:88,
      Author = {Harrison, P. G.},
      Title = {Function inversion},
      booktitle = PEMC,
      editor = BEJ,
      Publisher = N-H,
      Pages = {153--166},
      Year = {1988}
}


@article{HarrisonKoshnevisan:Acta92,
      author = {Harrison, P. G. and Khoshnevisan, H.},
      title = {On the Synthesis of Function Inverses},
      journal = {Acta Informatica},
      year = 1992,
      volume = 29,
      pages = {211--239},
}


@inproceedings{Romanenko:PEPM91,
      author = {Romanenko, A. Y.},
      title = {Inversion and Metacomputation},
      booktitle = {Partial Evaluation and Semantics-Based Program Manipulation, New
                                Haven, Connecticut (Sigplan Notices, vol. 26, no. 9, September
                                1991)},
      year = 1991,
      pages = {12--22},
      publisher = {New York:\ ACM},
}




                Torben

Return to the comp.compilers page.
Search the comp.compilers archives again.