Ultrametric Distance in Syntax



been applied. Perhaps the most important application is to taxonomy, Jardine
and Sibson (1971) Ch.7 [
17], and Sneath and Sokal (1973) [36]. Here the end of
a branch of the tree represents a species and the ultrametric distance between
them shows how closely the species are related. Hierarchical cluster methods
classify species and also shows how closely species are related. This technique
has also been used in semantics, Shepard and Arabie (1979) [
35]. The tech-
nique can become quite complicated because it involves statistical analysis with
continuous variates. Ultrametrics have been applied frequently in the theory of
spin glass, Weissman [
39]. Ultrametrics have been used for description of slowly
driven dissipative systems, which exhibit avalanche-like behaviour, these include
earthquakes, extinction events in biological evolution, and landscape formation,
Boettcher and Paiginski (1997) [
5]; also ultrametrics can describe systems with
fast relaxation, Vlad (1994) [
38]. Ultrametrics are used in the theory of neural
nets, Parga and Virasoro [
27]. The dynamics of random walks on ultrametric
spaces have been studied, Ogielchi and Stein (1985) [
26]. Ultrametrics have
been applied to the thermodynamics of macromolecules such as RNA, Higgs
(1996) [
15], and the directed polymer problem Perlman and Schwarz (1992)[28].
Bounds on the size of ultrametric structure have been discussed by Baldi and
Baun (1986) [
1]. From a more theoretical angle, a category theory approach
has been elucidated by Rutten (1996) [
34], and a model theoretic approach to
ultrametrics is given by Delon (1984) [
10]. The relationship between ultrametric
distance and hierarchy is further discussed in Guenoche (1997) [
11]. Construc-
tion of optimal ultrametric trees is discussed by Young and DeSarbo (1995)
[
40]. Ultrametrics are related to p-adelic quantities, Karwowski and Mendes
(1994) [
19]. P-adelic quantities are used in string theory: the way that ultra-
metrics enters here is explained in
§10&§13.4 of Bekke and Freund (1993) [2].
There does not seem to be any straightforward connection of any of the above
to the optimization techniques of Prince and Smolensky (1997) [
29]. As well
as ultrametric trees, there are also
decision trees Hammer (1998) [14], and the
connection between them is still not known. Some of the above ultrametric
applications have been reviewed by Rammal
et al (1986) [30].

1.2 Ultrametric Inequalities

There is the following relationship between trees and ultrametrics. An N -leaf
edge(node)-weighted tree corresponds to an
N × N square matrix M in which
Mij = the sum of the weights of the edges (nodes) in the shortest path between
i and j . When the weights are non-zero and non-negative, M is a distance in
the usual sense.

x, y, z Mxy = 0 if x = y                  (1)

Mxy 0 for x = y                         (2)

Mxy = Myx                              (3)

Mxy ≤ Mxz + Mzy.                         (4)



More intriguing information

1. Popular Conceptions of Nationhood in Old and New European
2. Modelling the health related benefits of environmental policies - a CGE analysis for the eu countries with gem-e3
3. Population ageing, taxation, pensions and health costs, CHERE Working Paper 2007/10
4. I nnovative Surgical Technique in the Management of Vallecular Cyst
5. Innovation Policy and the Economy, Volume 11
6. The role of statin drugs in combating cardiovascular diseases
7. The name is absent
8. The name is absent
9. The name is absent
10. The name is absent
11. The name is absent
12. Handling the measurement error problem by means of panel data: Moment methods applied on firm data
13. Macro-regional evaluation of the Structural Funds using the HERMIN modelling framework
14. Economies of Size for Conventional Tillage and No-till Wheat Production
15. Dendritic Inhibition Enhances Neural Coding Properties
16. AGRICULTURAL TRADE IN THE URUGUAY ROUND: INTO FINAL BATTLE
17. Competition In or For the Field: Which is Better
18. Co-ordinating European sectoral policies against the background of European Spatial Development
19. Climate change, mitigation and adaptation: the case of the Murray–Darling Basin in Australia
20. Global Excess Liquidity and House Prices - A VAR Analysis for OECD Countries