Automorphisms of the Planar Tree Power Series Algebra and the Non-Associative Logarithm

2000 Mathematics Subject Classification: 17A50, 05C05.

Bounds on isoperimetric values of trees

Let G = (V, E) be a finite, simple and undirected graph. For S subset of V, let delta(S, G) = {(u, v) is an element of E : u is an element of S and v is an element of V - S} be the edge boundary of S. Given an integer i, 1 <= i <= vertical bar V vertical bar, let the edge isoperimetric value of G at i be defined as b(e)(i, G) = min(S subset of V:vertical bar S vertical bar=i)vertical bar delta(S, G)vertical bar. The edge isoperimetric peak of G is defined as b(e)(G) = max(1 <= j <=vertical bar V vertical bar)b(e)(j, G). Let b(v)(G) denote the vertex isoperimetric peak defined in a corresponding way. The problem of determining a lower bound for the vertex isoperimetric peak in complete t-ary trees was recently considered in [Y. Otachi, K. Yamazaki, A lower bound for the vertex boundary-width of complete k-ary trees, Discrete Mathematics, in press (doi: 10.1016/j.disc.2007.05.014)]. In this paper we provide bounds which improve those in the above cited paper. Our results can be generalized to arbitrary (rooted) trees. The depth d of a tree is the number of nodes on the longest path starting from the root and ending at a leaf. In this paper we show that for a complete binary tree of depth d (denoted as T-d(2)), c(1)d <= b(e) (T-d(2)) <= d and c(2)d <= b(v)(T-d(2)) <= d where c(1), c(2) are constants. For a complete t-ary tree of depth d (denoted as T-d(t)) and d >= c log t where c is a constant, we show that c(1)root td <= b(e)(T-d(t)) <= td and c(2)d/root t <= b(v) (T-d(t)) <= d where c(1), c(2) are constants. At the heart of our proof we have the following theorem which works for an arbitrary rooted tree and not just for a complete t-ary tree. Let T = (V, E, r) be a finite, connected and rooted tree - the root being the vertex r. Define a weight function w : V -> N where the weight w(u) of a vertex u is the number of its successors (including itself) and let the weight index eta(T) be defined as the number of distinct weights in the tree, i.e eta(T) vertical bar{w(u) : u is an element of V}vertical bar. For a positive integer k, let l(k) = vertical bar{i is an element of N : 1 <= i <= vertical bar V vertical bar, b(e)(i, G) <= k}vertical bar. We show that l(k) <= 2(2 eta+k k)

Maximum Series-Parallel Subgraph

Consider the NP-hard problem of, given a simple graph G, to find a series-parallel subgraph of G with the maximum number of edges. The algorithm that, given a connected graph G, outputs a spanning tree of G, is a 1/2-approximation. Indeed, if n is the number of vertices in G, any spanning tree in G has n-1 edges and any series-parallel graph on n vertices has at most 2n-3 edges. We present a 7/12 -approximation for this problem and results showing the limits of our approach.

Static Balancing of Spring-loaded Planar Revolute-joint Linkages without Auxiliary Links

We present a method to statically balance a general treestructured,planar revolute-joint linkage loaded with linear springs or constant forces without using auxiliary links. The balancing methods currently documented in the literature use extra links; some do not apply when there are spring loads and some are restricted to only two-link serial chains. In our method, we suitably combine any non-zero-free-length load spring with another spring to result in an effective zero-free-length spring load. If a link has a single joint (with the parent link), we give a procedure to attach extra zero-free-length springs to it so that forces and moments are balanced for the link. Another consequence of this attachment is that the constraint force of the joint on the parent link becomes equivalent to a zero-free-length spring load. Hence, conceptually,for the parent link, the joint with its child is removed and replaced with the zero-free-length spring. This feature allows recursive application of this procedure from the end-branches of the tree down to the root, satisfying force and moment balance of all the links in the process. Furthermore, this method can easily be extended to the closed-loop revolute-joint linkages, which is also illustrated in the paper.

Wet bioadhesion in tree frogs

Viele Tiere wie etwa Geckos oder Laubfrösche können mittels ihrer Haftscheiben an Oberflächen kleben. Diese Haftscheiben ermöglichen es den Tieren, sich während ihrerrnFortbewegung an Oberflächen anzuheften und wieder zu lösen unabhängig von denrnvorherrschenden Umweltbedingungen. Frösche besitzen mikro- und nanostrukturierternsowie charakteristisch geformte Haftscheiben an Finger- und Zehenenden. Ihre besonderernevolutionäre Errungenschaft, sich stark und zugleich reversibel in sowohl trockenen alsrnauch feuchten Umgebungen anzuhaften, hat die Wissenschaft zur Nachahmung und Untersuchungrndieser Strukturen inspiriert. Zum besseren Verständnis der Mechanismen vonrnAnhaftung und Loslösung bei Laubfröschen wurden weiche, elastische und mikrostrukturierternOberflächen hergestellt, indem PDMS (Polydimethylsiloxan) auf einer Siliziummaskernmit Hexagonstruktur aufgetragen und vernetzt wurde. Dadurch wurden Anordnungenrnvon hexagonalen Mikrosäulen mit spezifischen geometrischen Eigenschaften undrnunterschiedlichen Kontaktgeometrien (normale, flache Form, T-Form und konkave Formrnder Säulenenden) erhalten. Um den Einfluss der van-der-Waals, hydrodynamischen,rnKapillar-und Adhäsionskräfte zu verstehen, wurden verschiedene experimentelle Ansätzernverfolgt: Die auf eine einzelne Säule wirkenden Adhäsionskräfte wurden mittelsrnRasterkraftmikroskopie gemessen. Dazu wurden speziell hergestellte kolloidale Sensorenrnverwendet. Diese Experimente wurden sowohl mit als auch ohne Flüssigkeitsfilm auf derrnSäule durchgeführt. Die Ergebnisse zeigten den Beitrag von Kapillarkraft und direktenrnKontaktkräften zur Adhäsionskraft bei Vorliegen eines Flüssigkeitsfilms. Die Adhäsionrnfiel umso größer aus, je weniger Flüssigkeit zwischen Sensor und Säule vorhanden war.rnIm Falle einer trockenen Adhäsion zeigte die Säule mit T-Form die höchste Adhäsion. Darndie Haftscheiben der Laubfrösche weich sind, können sie dynamisch ihre Form ändern,rnwas zu einer Änderung der hydrodynamischen Kraft zwischen Scheibe und Oberflächernführt. Der Einfluss der Oberflächenverformbarkeit auf die hydrodynamische Kraft wurderndaher am Modellsystem einer Kugel untersucht, welche sich einer weichen und ebenenrnOberfläche annähert. Dieses System wurde sowohl theoretisch über die Simulation finiterrnElemente als auch experimentell über die Messung mit kolloidalen Sonden untersucht.rnSowohl experimentelle Ergebnisse als auch die Simulationen ergaben eine Abnahme derrnhydrodynamischen Kraft bei Annäherung des kolloidalen Sensors an eine weiche undrnelastische Oberfläche. Beim Entfernen der Sensors von der Oberfläche verstärkte sichrndie hydrodynamische Anziehungskraft. Die Kraft, die zur Trennung eines Partikels von einer Oberfläche in Flüssigkeit notwendig ist, ist für weiche und elastischen Oberflächenrngrößer als für harte Oberflächen. In Bezug zur Bioadhäsion bei Laubfröschen konnternfestgestellt somit festgestellt werden, dass sich der hydrodynamische Anteil zur feuchtenrnBioadhäsion aufgrund der weichen Oberfläche erhöht. Weiterhin wurde der Einflussrndes Aspektverhältnisses der Säulen auf die Reibungskraft mittels eines kolloidalen Sensorsrnuntersucht. Gestreckte Säulen zeigten dabei eine höhere Reibung im Vergleich zu.rnSäulen mit einem gestreckten Hexagon als Querschnitt.

Root of the universal tree of life based on ancient aminoacyl-tRNA synthetase gene duplications.

Universal trees based on sequences of single gene homologs cannot be rooted. Iwabe et al. [Iwabe, N., Kuma, K.-I., Hasegawa, M., Osawa, S. & Miyata, T. (1989) Proc. Natl. Acad. Sci. USA 86, 9355-9359] circumvented this problem by using ancient gene duplications that predated the last common ancestor of all living things. Their separate, reciprocally rooted gene trees for elongation factors and ATPase subunits showed Bacteria (eubacteria) as branching first from the universal tree with Archaea (archaebacteria) and Eucarya (eukaryotes) as sister groups. Given its topical importance to evolutionary biology and concerns about the appropriateness of the ATPase data set, an evaluation of the universal tree root using other ancient gene duplications is essential. In this study, we derive a rooting for the universal tree using aminoacyl-tRNA synthetase genes, an extensive multigene family whose divergence likely preceded that of prokaryotes and eukaryotes. An approximately 1600-bp conserved region was sequenced from the isoleucyl-tRNA synthetases of several species representing deep evolutionary branches of eukaryotes (Nosema locustae), Bacteria (Aquifex pyrophilus and Thermotoga maritima) and Archaea (Pyrococcus furiosus and Sulfolobus acidocaldarius). In addition, a new valyl-tRNA synthetase was characterized from the protist Trichomonas vaginalis. Different phylogenetic methods were used to generate trees of isoleucyl-tRNA synthetases rooted by valyl- and leucyl-tRNA synthetases. All isoleucyl-tRNA synthetase trees showed Archaea and Eucarya as sister groups, providing strong confirmation for the universal tree rooting reported by Iwabe et al. As well, there was strong support for the monophyly (sensu Hennig) of Archaea. The valyl-tRNA synthetase gene from Tr. vaginalis clustered with other eukaryotic ValRS genes, which may have been transferred from the mitochondrial genome to the nuclear genome, suggesting that this amitochondrial trichomonad once harbored an endosymbiotic bacterium.

Preliminary evaluation of macadamia rootstocks for yield and tree height

Rootstock has profound effects on traits such as yield and tree size in various horticultural industries, however relatively little is known about rootstock effects for macadamia. In this study, 12 cultivars were propagated as open-pollinated seedling and clonal rootstocks, and own-rooted cuttings. The same cultivars were also used as scions, and grafted to a subset of rootstocks, then planted at four trial locations. In this preliminary analysis, rootstock accounted for 19% of the variance in yield compared with 72% for scion, and 23% in height compared with 72% for scion. There was no interaction between rootstock and scion for yield, and only a small effect for height. The interaction between rootstock and propagation method (seedling, clonal, own roots) was not significant for height. A small effect was observed for yield, with the own roots treatment producing significantly lower yield than grafted trees for all rootstock cultivars except 'HAES 849'. 'H2' seedling rootstock produced a cumulative yield to age 10 years of 11.1 kg tree -1 compared to the highest yield of 13.6 kg tree -1 for 'Beaumont' clonal rootstocks. 'H2' seedling rootstock produced 4.8 m trees at age 11 years, compared to the smallest grafted tree which was 'HAES 849' seedling at 4.7 m.

K-tree : large scale document clustering

We introduce K-tree in an information retrieval context. It is an efficient approximation of the k-means clustering algorithm. Unlike k-means it forms a hierarchy of clusters. It has been extended to address issues with sparse representations. We compare performance and quality to CLUTO using document collections. The K-tree has a low time complexity that is suitable for large document collections. This tree structure allows for efficient disk based implementations where space requirements exceed that of main memory.

How is a fruit tree like you? Using artistic metaphors to explore and develop emotional competence in children

Counselling children often requires the use of supplementary strategies in order to interest and engage the child in the therapeutic process. One such strategy is the Metaphorical Fruit Tree (MFT); an art metaphor suited to exploring and developing self-concept. Quantitative and qualitative data was used to explore the relationships between children’s ability to use metaphor, age, gender, and level of emotional competence (N = 58). Quantitative and qualitative analyses revealed a significant negative relationship between self-reported emotional competence and ability to use the MFT. It is proposed that children rely on different processes to understand self and as children’s ability to cognitively report on their emotional capabilities via the Emotional Competence Questionnaire (ECQ) increases, their ability to report creatively on those capabilities via the MFT is undermined. It is suggested that the MFT may be used, via creative processes and as an alternative to cognitive processes, to increase understanding and awareness of intrapersonal and interpersonal concepts of self in the child during counselling.

Document clustering with K-tree

This paper describes the approach taken to the XML Mining track at INEX 2008 by a group at the Queensland University of Technology. We introduce the K-tree clustering algorithm in an Information Retrieval context by adapting it for document clustering. Many large scale problems exist in document clustering. K-tree scales well with large inputs due to its low complexity. It offers promising results both in terms of efficiency and quality. Document classification was completed using Support Vector Machines.