首页 | 本学科首页   官方微博 | 高级检索  
     


Binary trees as a computational framework
Affiliation:1. University of Maribor;2. University of North Texas;1. Computer Laboratory, University of Cambridge, United Kingdom;2. Department of Mathematics & Computer Science, University of Catania, Italy;1. REQUIMTE (Rede de Química e Tecnologia), Laboratório de Toxicologia, Departamento de Ciências Biológicas, Faculdade de Farmácia, Universidade do Porto, Rua de Jorge Viterbo Ferreira, 228, 4050-313 Porto, Portugal;2. Farmacologia e Terapêutica Experimental, Instituto Biomédico de Investigação da Luz e Imagem (IBILI), Faculdade de Medicina, Universidade de Coimbra, 3000-548 Coimbra, Portugal;3. REQUIMTE (Rede de Química e Tecnologia), Laboratório de Química Aplicada, Departamento de Ciências Químicas, Faculdade de Farmácia, Universidade do Porto, Rua de Jorge Viterbo Ferreira, 228, 4050-313 Porto, Portugal;4. Faculdade de Ciências da Saúde, Universidade Fernando Pessoa, Rua Carlos da Maia, 296, 4200-150 Porto, Portugal;1. Institute for Logic, Language and Computation (ILLC), University of Amsterdam, P.O. Box 94242, 1090 GE Amsterdam, The Netherlands;2. Mathematical Institute, Utrecht University, P.O. Box 80010, 3508 TA Utrecht, The Netherlands
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 Gödel'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.
Keywords:Arithmetic computations with binary trees  Modeling computational abstractions with functional programming  Computations with balanced parenthesis languages
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号