Title: AN ARITHMETIC FOR ROOTED TREES

Speaker:    FABRIZIO LUCCIO

                                 Department of Informatics, University of Pisa

Time:      14:00-15:00, Oct. 12, 2017

Place:      Lecture Room 334, Level 3, Building No. 5, Institute of Software

Abstract:

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 show how 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, and show how to solve some tree equations as an introduction to the field. 

Finally we briefly discuss how our arithmetic might be useful in different applications.

To the best of our knowledge our proposal is new and is susceptible of variations and improvements.

FABRIZIO LUCCIO.  SCIENTIFIC CV

Emeritus Professor of Informatics at the University of Pisa, Italy.

Life Fellow of the IEEE.

Received an M.S. degree in electrical engineering from the Politecnico di Milano, in 1962, and a Ph.D. in electronic computers from the Italian university system in 1968.

       After an industrial experience with Olivetti, he taught and conducted research in various fields of C.S. at the Politecnico di Milano, M.I.T. (Project MAC), the University of Southern California, and New York University, before returning permanently to Italy at the University of Pisa, serving as department chairman and as coordinator of the Ph.D. program in Informatics.

He spent several sabbatical periods as a visiting professor at U.C.L.A., the University of Illinois, the National University of Singapore, Columbia University, and Carleton University in Canada. He has been a visiting scientist at T.J. Watson Research Center of IBM, USA for three terms, and a distinguished foreign scholar at the NTT LSI Laboratories in Morinosato, Japan, for one semester. He has given a very large number of invited lectures and conference presentations in many countries.

He pursued intense activities with UNESCO for the dissemination of informatics at university level in developing countries, and has been a delegate of the university of Pisa for international relations.

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.