License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FUN.2016.23
URN: urn:nbn:de:0030-drops-58687
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5868/
Go to the corresponding LIPIcs Volume Portal

Luccio, Fabrizio

An Arithmetic for Rooted Trees

pdf-format:
8.pdf (0.6 MB)

Abstract

We propose a new arithmetic for non-empty rooted unordered trees simply called trees. After discussing tree representation and enumeration, we define the operations of tree addition, multiplication, and stretch, prove their properties, and show that all trees can be generated from a starting tree of one vertex. We then show how a given tree can be obtained as the sum or product of two trees, thus defining prime trees with respect to addition and multiplication. In both cases we show how primality can be decided in time polynomial in the number of vertices and prove that factorization is unique.

We then define negative trees and suggest dealing with tree equations, giving some preliminary examples. Finally we comment on how our arithmetic might be useful, and discuss preceding studies that have some relations with ours. The parts of this work that do not concur to an immediate illustration of our proposal, including formal proofs, are reported in the Appendix.

To the best of our knowledge our proposal is completely new and can be largely modified in cooperation with the readers. To the ones of his age the author suggests that "many roads must be walked down before we call it a theory".

BibTeX - Entry

@InProceedings{luccio:LIPIcs:2016:5868,
  author =	{Fabrizio Luccio},
  title =	{{An Arithmetic for Rooted Trees}},
  booktitle =	{8th International Conference on Fun with Algorithms (FUN 2016)},
  pages =	{23:1--23:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-005-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{49},
  editor =	{Erik D. Demaine and Fabrizio Grandoni},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/5868},
  URN =		{urn:nbn:de:0030-drops-58687},
  doi =		{10.4230/LIPIcs.FUN.2016.23},
  annote =	{Keywords: Arithmetic, Rooted tree, Prime tree, Tree equation}
}

Keywords: Arithmetic, Rooted tree, Prime tree, Tree equation
Collection: 8th International Conference on Fun with Algorithms (FUN 2016)
Issue Date: 2016
Date of publication: 02.06.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI