LIPIcs.ICLP.2012.312.pdf
- Filesize: 429 kB
- 11 pages
Document
Deriving a Fast Inverse of the Generalized Cantor N-tupling Bijection
Author
-
Part of:
Volume:
Technical Communications of the 28th International Conference on Logic Programming (ICLP'12) (ICLP 2012)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Logic Programming (ICLP) - License:
Creative Commons Attribution-NoDerivs 3.0 Unported license
- Publication Date: 2012-09-05
Cite AsGet BibTex
Paul Tarau. Deriving a Fast Inverse of the Generalized Cantor N-tupling Bijection. In Technical Communications of the 28th International Conference on Logic Programming (ICLP'12). Leibniz International Proceedings in Informatics (LIPIcs), Volume 17, pp. 312-322, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)
https://doi.org/10.4230/LIPIcs.ICLP.2012.312
https://doi.org/10.4230/LIPIcs.ICLP.2012.312
Abstract
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 .
Keywords
- generalized Cantor n-tupling bijection
- bijective data type transformations
- combinatorial number system
- solving combinatorial problems in Prolog
- op
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads