License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICLP.2012.312
URN: urn:nbn:de:0030-drops-36326
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2012/3632/
Go to the corresponding LIPIcs Volume Portal

Tarau, Paul

Deriving a Fast Inverse of the Generalized Cantor N-tupling Bijection

pdf-format:
30.pdf (0.4 MB)

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 .

BibTeX - Entry

@InProceedings{tarau:LIPIcs:2012:3632,
  author =	{Paul Tarau},
  title =	{{Deriving a Fast Inverse of the Generalized Cantor N-tupling Bijection}},
  booktitle =	{Technical Communications of the 28th International Conference on Logic Programming (ICLP'12)},
  pages =	{312--322},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-43-9},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{17},
  editor =	{Agostino Dovier and V{\'i}tor Santos Costa},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2012/3632},
  URN =		{urn:nbn:de:0030-drops-36326},
  doi =		{10.4230/LIPIcs.ICLP.2012.312},
  annote =	{Keywords: generalized Cantor n-tupling bijection, bijective data type transformations, combinatorial number system, solving combinatorial problems in Prolog, op}
}

Keywords: generalized Cantor n-tupling bijection, bijective data type transformations, combinatorial number system, solving combinatorial problems in Prolog, op
Collection: Technical Communications of the 28th International Conference on Logic Programming (ICLP'12)
Issue Date: 2012
Date of publication: 05.09.2012

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI