Reseña: Deriving a fast inverse of the generalized Cantor N-tupling bijection

La semana que viene (6 de septiembre) se presentará en el ICLP’12 (28th International Conference on Logic Programming) un trabajo sobre resolución lógica de problemas combinatorios titulado Deriving a fast inverse of the generalized Cantor N-tupling bijection.

Su autor es Paul Tarau (de la University of North Texas, Denton, Texas, USA).

Su resumen es

We attack an interesting open problem (an efficient algorithm to invert the generalized Cantor N-tupling bijection) and solve it through a sequence of equivalence preserving transformations of logic programs, that take advantage of unique strengths of this programming paradigm. An extension to set and multiset tuple encodings, as well as a simple application to a “fair-search” mechanism illustrate practical uses of our algorithms.

The code in the paper (a literate Prolog program, tested with SWI-Prolog and Lean Prolog) is available at http://logic.cse.unt.edu/tarau/research/2012/pcantor.pl.