
A semantic construction of twoary integers (TR)Gabriele RicciAbstract:To binary trees, twoary integers are what usual integers are to natural numbers, seen as unary trees. We can represent twoary integers as binary trees too, yet with leaves labelled by binary words and with a structural restriction. In a sense, they are simpler than the binary trees, they relativize. Hence, contrary to the extensions known from Arithmetic and Algebra, this integer extension does not make the starting objects more complex.We use a semantic construction to get this extension. This method differs from the algebraic ones, mainly because it is able to find equational features of the extended objects. Twoary integers turn out to form the free algebra corresponding to the JónssonTarski's ``paradoxical'' equations. This entails that they have a sum extending the usual sum as well as other operations of higher ``dimensions''. In Programming, we use usual integers as address jumps for a direct access usual (``unary'') memory. Such a memory differs from the (virtual) memory of LISP programming language which is both binary and sequential (to reach a location we need to pass through intermediate locations). Even unary memories can be sequential (the tape of a Turing machine), yet we know that a direct access one works better. This carries over to the binary case: twoary integers can provide LISP memories with convenient direct access jumps and the above low complexity hints at feasible hardware implementations.
Available: PDF and DVI. [Page last updated on January 19, 2013, 08:05:37.] 

Enea Zaffanella 
Home  People  Projects  Publications  Seminars  Software  Links 