Paper Info
Title
Binary trees as a computational framework
Abstract
We present a new set of algorithms for performing arithmetic computations on the set of natural numbers, represented as ordered rooted binary trees. We show formally that these algorithms are correct and discuss their time and space complexity in comparison to traditional arithmetic operations on bitstrings. Our binary tree algorithms follow the structure of a simple type language, similar to that of Godel's System T. Generic implementations using Haskell's type class mechanism are shared between instances shown to be isomorphic to the set of natural numbers. This representation independence is illustrated by instantiating our computational framework to the language of balanced parenthesis languages. The self-contained source code of the paper is available at http://logic.cse.unt.edu/tarau/research/2012/jtypes.hs.
Year
DOI
Venue
2013
10.1016/j.cl.2013.08.002
Computer Languages, Systems & Structures
Keywords
Field
DocType
arithmetic computation,binary tree algorithm,binary tree,computational framework,traditional arithmetic operation,natural number,type class mechanism,simple type language,balanced parenthesis language,new set,system t. generic
Natural number,Programming language,Computer science,Source code,Arbitrary-precision arithmetic,Binary tree,Theoretical computer science,Isomorphism,Haskell,Binary number,Computation
Journal
Volume
Issue
ISSN
39
4
1477-8424
Citations 
PageRank 
References 
2
0.41
14
Authors
2
Name
Order
Citations
PageRank
David Haraburda191.49
Paul Tarau21529113.14