Scala package for Ranking and Unranking of Term Algebras

[Paul Tarau]

I have just released as an open source Google code project
a Scala package supporting algorithms that implement bijections
between natural numbers and term algebras, at:

http://code.google.com/p/bijective-goedel-numberings/

These encodings (also called ranking / unranking functions by combinatorialists
and Goedel numberings by logicians) can be of practical use for succinct serialization
of data types (including for remote messaging between actors) and generation of
random terms for automated testing.

The code is quite efficient due to a novel algorithm computing the inverse of the
generalized Cantor bijection between N^k and N (the only such encoding known
to be polynomial).

Enjoy,

Paul Tarau
 
P.S. And using anything other than Scala to get this stuff right and fast would have
been much, much harder :-)

[Alexander Pupeikis]

Hello Paul,

can you please provide more examples of usage of your library? Would be much appreciated.

Thank you very much!

-- 

Alexander

[Paul Tarau]

Hello Alexander,

Besides the possible uses I have mentioned (serialization to succinct messages and genration of random terms),  the code dealing with fixed signature terms at:

http://code.google.com/p/bijective-goedel-numberings/source/browse/src/bijectiveGoedelNumberings/FixedSignatureTerm.scala

can be used to exhaustively enumerate all small  circuits using a library of logic gates - see examples of use in

http://code.google.com/p/bijective-goedel-numberings/source/browse/src/bijectiveGoedelNumberings/Main.scala

Paul