Home |
People |
Projects |
Publications |
Seminars |
Software |
Links |
A semantic construction of two-ary integers (TR)
Gabriele RicciAbstract:
To binary trees, two-ary integers are what usual integers are to natural numbers, seen as unary trees. We can represent two-ary 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. Two-ary integers turn out to form the free algebra corresponding to the Jónsson-Tarski'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: two-ary 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