BZPEERReading, trust and collaboration for researchDiscover
Workspaces
Network
Opportunities
Account
Researcher profile
Fabrizio Luccio contributes to research discovery and scholarly infrastructure.
Trust snapshot
Actions
Research graph
Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
Some simple facts are proved ruling the Collatz tree and the chains of vertices appearing in it, leading to the reduction of the number of significant elements appearing in the tree. Although the Collatz conjecture remains open, these fact may cast some light on the nature of the problem.
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 we prove that factorization is unique. We then define negative trees and suggest dealing with tree equations, giving some preliminary results. Finally we comment on how our arithmetic might be useful, and discuss preceding studies that have some relations with our. To the best of our knowledge our approach and results are completely new aside for an earlier version of this work submitte as an arXiv manuscript.
As well known the rotation distance D(S,T) between two binary trees S, T of n vertices is the minimum number of rotations of pairs of vertices to transform S into T. We introduce the new operation of chain rotation on a tree, involving two chains of vertices, that requires changing exactly three pointers in the data structure as for a standard rotation, and define the corresponding chain distance C(S,T). As for D(S,T), no polynomial time algorithm to compute C(S,T) is known. We prove a constructive upper bound and an analytical lower bound on C(S,T) based on the number of maximal chains in the two trees. In terms of n we prove the general upper bound C(S,T)<= n-1 and we show that there are pairs of trees for which this bound is tight. No similar result is known for D(S,T) where the best upper and lower bounds are 2n-6 and 5n/3-4 respectively.
Given a Boolean function f on n variables, a Disjoint Sum-of-Products (DSOP) of f is a set of products (ANDs) of subsets of literals whose sum (OR) equals f, such that no two products cover the same minterm of f. DSOP forms are a special instance of partial DSOPs, i.e. the general case where a subset of minterms must be covered exactly once and the other minterms (typically corresponding to don't care conditions of $f$) can be covered any number of times. We discuss finding DSOPs and partial DSOP with a minimal number of products, a problem theoretically connected with various properties of Boolean functions and practically relevant in the synthesis of digital circuits. Finding an absolute minimum is hard, in fact we prove that the problem of absolute minimization of partial DSOPs is NP-hard. Therefore it is crucial to devise a polynomial time heuristic that compares favorably with the known minimization tools. To this end we develop a further piece of theory starting from the definition of the weight of a product p as a functions of the number of fragments induced on other cubes by the selection of p, and show how product weights can be exploited for building a class of minimization heuristics for DSOP and partial DSOP synthesis. A set of experiments conducted on major benchmark functions show that our method, with a family of variants, always generates better results than the ones of previous heuristics, including the method based on a BDD representation of f.