中科院数学与系统科学研究院

数学研究所

中科院管理、决策和信息系统重点实验室

学术报告会

报告人：Prof. Fabrizio Luccio   (意大利比萨大学)

题  目：Arithmetic for Rooted Trees

时  间：2017.10.16（星期一），10:00-11:00

地  点：数学院南楼N205室

摘要：

We introduce a new arithmetic for non-empty rooted unordered trees. After discussing tree representation and enumeration, we define the operations of tree addition, multiplication, and stretch, and prove their properties. Using these operations all trees can be generated from a starting tree of one vertex. We show how a given tree can be obtained as the sum or as the product of two trees, and define 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 introduce tree equations whose coefficients are integers and whose unknowns are trees. We show how to solve some tree equations as an introduction to the field, and suggest more advanced examples. Finally we briefly discuss how our arithmetic might be useful in different applications. To the best of our knowledge our proposal is new and may be susceptible of variations and improvements.

简历：

FABRIZIO LUCCIO Professor of Informatics at the University of Pisa, Italy. Life Fellow of the IEEE. For a long time his major scientific interest has been in computing systems, particularly in parallel and distributed processing. It is now in algorithm and data structures, with attention to Web problems. He is the author of more than one hundred and eighty papers published in major international research journals and conference proceedings, of five university text books in theoretical computer, and of two books on scientific culture at large. He received many scientific and academic prizes, and is an honorary professor of several universities worldwide.