Resource allocation in rooted trees for VLSI applications

ABSTRACT

Several optimization problems of modifying the weight of vertices in rooted trees, some of which are special cases of the inverse 1-median problem, are solved. Such problems arise in Very Large Scale Integration (VLSI) design of hardware security circuits, circuit synchronization, and analog-to-digital converters. These problems require assigning costly hardware (demands) to the leaves of rooted trees. One common property of these problems is that a resource allocated to an internal node can be shared by the entire sub-tree emanated at the node. Two types of problems are studied here. (1) A tree node employs an addition operation and the demands at the leaves are obtained by summing the resources allocated to nodes along the root-to-leaf paths. A linear-time bottom-up algorithm is shown to minimize the total resources allocated to tree nodes. (2) A tree’s node employs a multiplication operation and the demands at the leaves are obtained by multiplying the resources allocated to nodes along the root-to-leaf paths. A bottom-up dynamic programming algorithm is shown to minimize the total resources allocated to the tree’s nodes. While the above problems are usually solved by design engineers heuristically, this paper offers optimal solutions that can be easily programmed in CAD tools.     

Inverse sequences, rooted trees and their end spaces

In this paper we prove that if we consider the standard real metric on simplicial rooted trees then the category Tower-Set of inverse sequences can be described by means of the bounded coarse geometry of the naturally associated trees. Using this we give a geometrical characterization of Mittag-Leffler property in inverse sequences in terms of the metrically proper homotopy type of the corresponding tree and its maximal geodesically complete subtree. We also obtain some consequences in shape theory. In particular we describe some new representations of shape morphisms related to infinite branches in trees.     

Path ideals of rooted trees and their graded Betti numbers

Let Γ be a rooted (and directed) tree, and let t be a positive integer. The path ideal It(Γ) is generated by monomials that correspond to directed paths of length (t−1) in Γ. In this paper, we study algebraic properties and invariants of It(Γ). We give a recursive formula to compute the graded Betti numbers of It(Γ) in terms of path ideals of subtrees. We also give a general bound for the regularity, explicitly compute the linear strand, and investigate when It(Γ) has a linear resolution.     

Vector lattices and rooted trees

There is a 1-1-correspondence between isomorphism classes of finite dimensional vector lattices and finite rooted unlabelled trees. Thus the problem of counting isomorphism classes of finite dimensional vector lattices reduces to the well-known combinatorial problem of counting these trees. The correspondence is used to identify the class of congruence lattices of finite-dimensional vector lattices as the class of finite dual relative Stone algebras, in partial answer to a question posed by Birkhoff.Dedicated to the memory of Alan DayPresented by J. Sichler.     

Reznichenko families of trees and their applications

Examples of Talagrand, Gul'ko and Corson compacta resulting from Reznichenko families of trees are presented. The K_σδ property for weakly -analytic Banach spaces with an unconditional basis is proved.     

Combinatorics of rooted trees and Hopf algebras

We begin by considering the graded vector space with a basis consisting of rooted trees, with grading given by the count of non-root vertices. We define two linear operators on this vector space, the growth and pruning operators, which respectively raise and lower grading; their commutator is the operator that multiplies a rooted tree by its number of vertices, and each operator naturally associates a multiplicity to each pair of rooted trees. By using symmetry groups of trees we define an inner product with respect to which the growth and pruning operators are adjoint, and obtain several results about the associated multiplicities.

Now the symmetric algebra on the vector space of rooted trees (after a degree shift) can be endowed with a coproduct to make a Hopf algebra; this was defined by Kreimer in connection with renormalization. We extend the growth and pruning operators, as well as the inner product mentioned above, to Kreimer's Hopf algebra. On the other hand, the vector space of rooted trees itself can be given a noncommutative multiplication: with an appropriate coproduct, this leads to the Hopf algebra of Grossman and Larson. We show that the inner product on rooted trees leads to an isomorphism of the Grossman-Larson Hopf algebra with the graded dual of Kreimer's Hopf algebra, correcting an earlier result of Panaite.

     

Order quasisymmetric functions distinguish rooted trees

Richard P. Stanley conjectured that finite trees can be distinguished by their chromatic symmetric functions. In this paper, we prove an analogous statement for posets: Finite rooted trees can be distinguished by their order quasisymmetric functions.     

Ordered partitions and drawings of rooted plane trees

We study the bounded regions in a generic slice of the hyperplane arrangement in Rⁿ${\mathbb{R}}^n$ consisting of the hyperplanes defined by _xi$x_i$ and _xi+_xj$x_i+x_j$. The bounded regions are in bijection with several classes of combinatorial objects, including the ordered partitions of [n]$\left[n\right]$ all of whose left-to-right minima occur at odd locations and the drawings of rooted plane trees with n+1$n+1$ vertices. These are sequences of rooted plane trees such that each tree in a sequence can be obtained from the next one by removing a leaf.     

Categorification of Hopf algebras of rooted trees

We exhibit a monoidal structure on the category of finite sets indexed by P-trees for a finitary polynomial endofunctor P. This structure categorifies the monoid scheme (over Spec ?) whose semiring of functions is (a P-version of) the Connes-Kreimer bialgebra H of rooted trees (a Hopf algebra after base change to ? and collapsing H ₀). The monoidal structure is itself given by a polynomial functor, represented by three easily described set maps; we show that these maps are the same as those occurring in the polynomial representation of the free monad on P.     

On the spectra of certain rooted trees

Let T be an unweighted tree with vertex root v which is the union of two trees T₁=(V₁,E₁), T₂=(V₂,E₂) such that V₁ ∩ V₂ = {v} and T₁ and T₂ have the property that the vertices in each of their levels have equal degree. We characterize completely the eigenvalues of the adjacency matrix and of the Laplacian matrix of T. They are the eigenvalues of symmetric tridiagonal matrices whose entries are given in terms of the vertex degrees. Moreover, we give some results about the multiplicity of the eigenvalues. Applications to some particular trees are developed.     

Ergodic decomposition of group actions on rooted trees

We prove a general result about the decomposition into ergodic components of group actions on boundaries of spherically homogeneous rooted trees. Namely, we identify the space of ergodic components with the boundary of the orbit tree associated with the action, and show that the canonical system of ergodic invariant probability measures coincides with the system of uniform measures on the boundaries of minimal invariant subtrees of the tree. Special attention is paid to the case of groups generated by finite automata. Few examples, including the lamplighter group, Sushchansky group, and so-called universal group, are considered in order to demonstrate applications of the theorem.     

Dimension and randomness in groups acting on rooted trees

We explore the structure of the -adic automorphism group of the infinite rooted regular tree. We determine the asymptotic order of a typical element, answering an old question of Turán.

We initiate the study of a general dimension theory of groups acting on rooted trees. We describe the relationship between dimension and other properties of groups such as solvability, existence of dense free subgroups and the normal subgroup structure. We show that subgroups of generated by three random elements are full dimensional and that there exist finitely generated subgroups of arbitrary dimension. Specifically, our results solve an open problem of Shalev and answer a question of Sidki.

     

The automorphism tower of groups acting on rooted trees

The group of isometries of a rooted -ary tree, and many of its subgroups with branching structure, have groups of automorphisms induced by conjugation in . This fact has stimulated the computation of the group of automorphisms of such well-known examples as the group studied by R. Grigorchuk, and the group studied by N. Gupta and the second author.

In this paper, we pursue the larger theme of towers of automorphisms of groups of tree isometries such as and . We describe this tower for all subgroups of which decompose as infinitely iterated wreath products. Furthermore, we fully describe the towers of and .

More precisely, the tower of is infinite countable, and the terms of the tower are -groups. Quotients of successive terms are infinite elementary abelian -groups.

In contrast, the tower of has length , and its terms are -groups. We show that is an elementary abelian -group of countably infinite rank, while .