Recognition of Robinsonian dissimilarities

We present an O(n ³)-time, O(n ²)-space algorithm to test whether a dissimilarity d on an n-object set X is Robinsonian, i.e., X admits an ordering such that i≤j≤k implies that d(x _i,x_k)≥max {d(x_i,x_j),d(x_j,x_k)}.     

An Optimal Algorithm To Recognize Robinsonian Dissimilarities

A dissimilarity D on a finite set S is said to be Robinsonian if S can be totally ordered in such a way that, for every i < j < k, D (i, j) ≤ D (i, k) and D (j, k) ≤ D (i, k). Intuitively, D is Robinsonian if S can be represented by points on a line. Recognizing Robinsonian dissimilarities has many applications in seriation and classification. In this paper, we present an optimal O (n ²) algorithm to recognize Robinsonian dissimilarities, where n is the cardinal of S. Our result improves the already known algorithms.     

Optimal algorithms for comparing trees with labeled leaves

LetR _n denote the set of rooted trees withn leaves in which: the leaves are labeled by the integers in {1, ...,n}; and among interior vertices only the root may have degree two. Associated with each interior vertexv in such a tree is the subset, orcluster, of leaf labels in the subtree rooted atv. Cluster {1, ...,n} is calledtrivial. Clusters are used in quantitative measures of similarity, dissimilarity and consensus among trees. For anyk trees inR _n , thestrict consensus tree C(T ₁, ...,T _k ) is that tree inR _n containing exactly those clusters common to every one of thek trees. Similarity between treesT ₁ andT ₂ inR _n is measured by the numberS(T ₁,T ₂) of nontrivial clusters in bothT ₁ andT ₂; dissimilarity, by the numberD(T ₁,T ₂) of clusters inT ₁ orT ₂ but not in both. Algorithms are known to computeC(T ₁, ...,T _k ) inO(kn ²) time, andS(T ₁,T ₂) andD(T ₁,T ₂) inO(n ²) time. I propose a special representation of the clusters of any treeT R _n , one that permits testing in constant time whether a given cluster exists inT. I describe algorithms that exploit this representation to computeC(T ₁, ...,T _k ) inO(kn) time, andS(T ₁,T ₂) andD(T ₁,T ₂) inO(_n) time. These algorithms are optimal in a technical sense. They enable well-known indices of consensus between two trees to be computed inO(n) time. All these results apply as well to comparable problems involving unrooted trees with labeled leaves.The Natural Sciences and Engineering Research Council of Canada partially supported this work with grant A-4142.     

Weighted Graphs with Distances in Given Ranges

Let \( \mathcal{G} \) = (G,w) be a weighted simple finite connected graph, that is, let G be a simple finite connected graph endowed with a function w from the set of the edges of G to the set of real numbers. For any subgraph G′ of G, we define w(G′) to be the sum of the weights of the edges of G′. For any i, j vertices of G, we define D _{i,j}(\( \mathcal{G} \)) to be the minimum of the weights of the simple paths of G joining i and j. The D _{i,j}(\( \mathcal{G} \)) are called 2-weights of \( \mathcal{G} \). Weighted graphs and their reconstruction from 2-weights have applications in several disciplines, such as biology and psychology.Let \( {\left\{{m}_I\right\}}_{I\in \left(\frac{\left\{1,\dots, n\right\}}{2}\right)} \) and \( {\left\{{M}_I\right\}}_{I\in \left(\frac{\left\{1,\dots, n\right\}}{2}\right)} \) be two families of positive real numbers parametrized by the 2-subsets of {1, …, n} with m _I ≤ M _I for any I; we study when there exist a positive-weighted graph G and an n-subset {1, …, n} of the set of its vertices such that D _I (\( \mathcal{G} \)) ∈ [m _I ,M _I ] for any \( I\in \left(\frac{\left\{1,\dots, n\right\}}{2}\right) \). Then we study the analogous problem for trees, both in the case of positive weights and in the case of general weights.     

Axiomatization and Models of Scientific Theories

In this paper we discuss two approaches to the axiomatization of scientific theories in the context of the so called semantic approach, according to which (roughly) a theory can be seen as a class of models. The two approaches are associated respectively to Suppes’ and to da Costa and Chuaqui’s works. We argue that theories can be developed both in a way more akin to the usual mathematical practice (Suppes), in an informal set theoretical environment, writing the set theoretical predicate in the language of set theory itself or, more rigorously (da Costa and Chuaqui), by employing formal languages that help us in writing the postulates to define a class of structures. Both approaches are called internal, for we work within a mathematical framework, here taken to be first-order ZFC. We contrast these approaches with an external one, here discussed briefly. We argue that each one has its strong and weak points, whose discussion is relevant for the philosophical foundations of science.     

Unfolding a symmetric matrix

Graphical displays which show inter-sample distances are important for the interpretation and presentation of multivariate data. Except when the displays are two-dimensional, however, they are often difficult to visualize as a whole. A device, based on multidimensional unfolding, is described for presenting some intrinsically high-dimensional displays in fewer, usually two, dimensions. This goal is achieved by representing each sample by a pair of points, sayR _i andr _i, so that a theoretical distance between thei-th andj-th samples is represented twice, once by the distance betweenR _i andr _j and once by the distance betweenR _j andr _i. Selfdistances betweenR _i andr _i need not be zero. The mathematical conditions for unfolding to exhibit symmetry are established. Algorithms for finding approximate fits, not constrained to be symmetric, are discussed and some examples are given.     

Recognizing Treelike k-Dissimilarities

A k-dissimilarity D on a finite set X, |X|????k, is a map from the set of size k subsets of X to the real numbers. Such maps naturally arise from edgeweighted trees T with leaf-set X: Given a subset Y of X of size k, D(Y ) is defined to be the total length of the smallest subtree of T with leaf-set Y . In case k?=?2, it is well-known that 2-dissimilarities arising in this way can be characterized by the so-called ??4-point condition??. However, in case k?>?2 Pachter and Speyer (2004) recently posed the following question: Given an arbitrary k-dissimilarity, how do we test whether this map comes from a tree? In this paper, we provide an answer to this question, showing that for k????3 a k-dissimilarity on a set X arises from a tree if and only if its restriction to every 2?k-element subset of X arises from some tree, and that 2?k is the least possible subset size to ensure that this is the case. As a corollary, we show that there exists a polynomial-time algorithm to determine when a k-dissimilarity arises from a tree. We also give a 6-point condition for determining when a 3-dissimilarity arises from a tree, that is similar to the aforementioned 4-point condition.     

Non-Monotonic Set Theory as a Pragmatic Foundation of Mathematics

In this paper I propose a new approach to the foundation of mathematics: non-monotonic set theory. I present two completely different methods to develop set theories based on adaptive logics. For both theories there is a finitistic non-triviality proof and both theories contain (a subtle version of) the comprehension axiom schema. The first theory contains only a maximal selection of instances of the comprehension schema that do not lead to inconsistencies. The second allows for all the instances, also the inconsistent ones, but restricts the conclusions one can draw from them in order to avoid triviality. The theories have enough expressive power to form a justification/explication for most of the established results of classical mathematics. They are therefore not limited by Gödel’s incompleteness theorems. This remarkable result is possible because of the non-recursive character of the final proofs of theorems of non-monotonic theories. I shall argue that, precisely because of the computational complexity of these final proofs, we cannot claim that non-monotonic theories are ideal foundations for mathematics. Nevertheless, thanks to their strength, first order language and the recursive dynamic (defeasible) proofs of theorems of the theory, the non-monotonic theories form (what I call) interesting pragmatic foundations.     

An efficient algorithm for supertrees

Givenk rooted binary treesA ₁, A₂, ..., A_k, with labeled leaves, we generateC, a unique system of lineage constraints on common ancestors. We then present an algorithm for constructing the set of rooted binary treesB, compatible with all ofA ₁, A₂, ..., A_k. The running time to obtain one such supertree isO(k ² n²), wheren is the number of distinct leaves in all of the treesA ₁, A₂, ..., A_k.     

Computational empiricism

I argue here for a number of ways that modern computational science requires a change in the way we represent the relationship between theory and applications. It requires a switch away from logical reconstruction of theories in order to take surface mathematical syntax seriously. In addition, syntactically different versions of the same theory have important differences for applications, and this shows that the semantic account of theories is inappropriate for some purposes. I also argue against formalist approaches in the philosophy of science and for a greater role for perceptual knowledge rather than propositional knowledge in scientific empiricism.The term computational empiricism was suggested to me in conversation at a philosophy conference in Venice, Italy in June 1991 by someone whose name I have unfortunately forgotten. It seemed to capture perfectly the set of techniques I had described in my talk there, and I have since adopted it. I thank the originator of this term, whoever he is.     

Bolzano’s Infinite Quantities

In his Foundations of a General Theory of Manifolds, Georg Cantor praised Bernard Bolzano as a clear defender of actual infinity who had the courage to work with infinite numbers. At the same time, he sharply criticized the way Bolzano dealt with them. Cantor’s concept was based on the existence of a one-to-one correspondence, while Bolzano insisted on Euclid’s Axiom of the whole being greater than a part. Cantor’s set theory has eventually prevailed, and became a formal basis of contemporary mathematics, while Bolzano’s approach is generally considered a step in the wrong direction. In the present paper, we demonstrate that a fragment of Bolzano’s theory of infinite quantities retaining the part-whole principle can be extended to a consistent mathematical structure. It can be interpreted in several possible ways. We obtain either a linearly ordered ring of finite and infinitely great quantities, or a partially ordered ring containing infinitely small, finite and infinitely great quantities. These structures can be used as a basis of the infinitesimal calculus similarly as in non-standard analysis, whether in its full version employing ultrafilters due to Abraham Robinson, or in the recent “cheap version” avoiding ultrafilters due to Terence Tao.     

Leibniz’s Theory of Space

In this paper I offer a fresh interpretation of Leibniz’s theory of space, in which I explain the connection of his relational theory to both his mathematical theory of analysis situs and his theory of substance. I argue that the elements of his mature theory are not bare bodies (as on a standard relationalist view) nor bare points (as on an absolutist view), but situations. Regarded as an accident of an individual body, a situation is the complex of its angles and distances to other co-existing bodies, founded in the representation or state of the substance or substances contained in the body. The complex of all such mutually compatible situations of co-existing bodies constitutes an order of situations, or instantaneous space. Because these relations of situation change from one instant to another, space is an accidental whole that is continuously changing and becoming something different, and therefore a phenomenon. As Leibniz explains to Clarke, it can be represented mathematically by supposing some set of existents hypothetically (and counterfactually) to remain in a fixed mutual relation of situation, and gauging all subsequent situations in terms of transformations with respect to this initial set. Space conceived in terms of such allowable transformations is the subject of Analysis Situs. Finally, insofar as space is conceived in abstraction from any bodies that might individuate the situations, it encompasses all possible relations of situation. This abstract space, the order of all possible situations, is an abstract entity, and therefore ideal.     

The Metric Cutpoint Partition Problem

Let G = (V, E,w) be a graph with vertex and edge sets V and E, respectively, and w: E → a function which assigns a positive weight or length to each edge of G. G is called a realization of a finite metric space (M, d), with M = {1, ..., n} if and only if {1, ..., n} ⊆ V and d(i, j) is equal to the length of the shortest chain linking i and j in G ∀i, j = 1, ..., n. A realization G of (M, d), is called optimal if the sum of its weights is minimal among all the realizations of (M, d). A cutpoint in a graph G is a vertex whose removal strictly increases the number of connected components of G. The Metric Cutpoint Partition Problem is to determine if a finite metric space (M, d) has an optimal realization containing a cutpoint. We prove in this paper that this problem is polynomially solvable. We also describe an algorithm that constructs an optimal realization of (M, d) from optimal realizations of subspaces that do not contain any cutpoint. Supported by grant PA002-104974/2 from the Swiss National Science Foundation. Published online xx, xx, xxxx.     

奎因的整体知识论及其后果

奎因通过“语义上溯”,在“观察句”和“观察陈述”层面上建立外部刺激与科学理论之间的证据联系来解决知识论问题。奎因认为,由于观察范畴的假并不提供结论性的反驳,因而在理论和预言矛盾的情况下,我们绝不能指出某些引起这些矛盾的句子,相反,科学理论始终是作为整体的系统要么受到怀疑,要么被修正;科学认识中没有分析命题和综合命题的区分,也没有还原论的确证路径,哲学家和科学家在一条破船上航行,没有起点也没有终点。     

Gödel, Einstein, Mach: Casting Constraints on All-embracing Concepts

Can a theory turn back, as it were, upon itselfand vouch for its own features? That is, canthe derived elements of a theory be the veryprimitive terms that provide thepresuppositions of the theory? This form of anall-embracing feature assumes a totality inwhich there occurs quantification over thattotality, quantification that is defined bythis very totality. I argue that the Machprinciple exhibits such a feature ofall-embracing nature. To clarify the argument,I distinguish between on the one handcompleteness and on the other wholeness andtotality, as different all-embracing features:the former being epistemic while the latter –ontological. I propose an analogy between the Mach principleas a possible selection principle in generalrelativity, and the vicious-circle principle infoundations of mathematics. I finally concludewith a consequence of this analogyvis-à-vis completeness and totality,viz., both should be constrained if they wereto be valid concepts for a physical theory. The paper progresses chronologically. Itfocuses on the physical approach of Mach thatformed the background for Einstein's generaltheory of relativity. The solutions of thefield equations in the form of cosmologicalmodels set the scene for the view ofall-embracing concepts discussed in the paper.Specifically, the ideas encapsulated in whatEinstein called the Mach principle, constitutethe thread of this account. The principle isfound however to falter, in view of the factthat there are several different types ofsolution of the field equations that contradictit. One such important cosmological model withramifying consequences is the rotational masssolution of Gödel. The question arises asto whether there is an analogy betweenincompleteness in foundations of mathematicsand in physics? The analogy between the vicious-circleprinciple and the Mach principle demonstratesan affirmative answer which suggests in turnthat completeness and totality must becurtailed – that is, conditions and limitsshould be imposed on completeness and totalityto render them valid for physical theories.     

An Algorithm for Computing Cutpoints in Finite Metric Spaces

The theory of the tight span, a cell complex that can be associated to every metric D, offers a unifying view on existing approaches for analyzing distance data, in particular for decomposing a metric D into a sum of simpler metrics as well as for representing it by certain specific edge-weighted graphs, often referred to as realizations of D. Many of these approaches involve the explicit or implicit computation of the so-called cutpoints of (the tight span of) D, such as the algorithm for computing the “building blocks” of optimal realizations of D recently presented by A. Hertz and S. Varone. The main result of this paper is an algorithm for computing the set of these cutpoints for a metric D on a finite set with n elements in O(n3) time. As a direct consequence, this improves the run time of the aforementioned O(n6)-algorithm by Hertz and Varone by “three orders of magnitude”.     

Minimum spanning trees for tree metrics: abridgements and adjustments

Two properties of tree metrics are already known in the literature: tree metrics on a setX withn elements have 2n?3 degrees of freedom; a tree metric has Robinson form with regard to its minimum spanning tree (MST), or to any such MST if several of them exist. Starting from these results, we prove that a tree metrict is entirely defined by its restriction to some setB of 2n?3 entries. This set is easily determined from the table oft and includes then?1 entries of an MST. A fast method for the adjustment of a tree metric to any given metricd is then obtained. This method extends to dissimilarities.     

Perceiving the Infinite and the Infinitesimal World: Unveiling and Optical Diagrams in Mathematics

Many important concepts of the calculus are difficult to grasp, and they may appear epistemologically unjustified. For example, how does a real function appear in “small” neighborhoods of its points? How does it appear at infinity? Diagrams allow us to overcome the difficulty in constructing representations of mathematical critical situations and objects. For example, they actually reveal the behavior of a real function not “close to” a point (as in the standard limit theory) but “in” the point. We are interested in our research in the diagrams which play an optical role –microscopes and “microscopes within microscopes”, telescopes, windows, a mirror role (to externalize rough mental models), and an unveiling role (to help create new and interesting mathematical concepts, theories, and structures). In this paper we describe some examples of optical diagrams as a particular kind of epistemic mediator able to perform the explanatory abductive task of providing a better understanding of the calculus, through a non-standard model of analysis. We also maintain they can be used in many other different epistemological and cognitive situations.     

The Surveyability of Long Proofs

The specific characteristics of mathematical argumentation all depend on the centrality that writing has in the practice of mathematics, but blindness to this fact is near universal. What follows concerns just one of those characteristics, justification by proof. There is a prevalent view that long proofs pose a problem for the thesis that mathematical knowledge is justified by proof. I argue that there is no such problem: in fact, virtually all the justifications of mathematical knowledge are ‘long proofs’, but because these real justifications are distributed in the written archive of mathematics, proofs remain surveyable, hence good.     

Induction from a Single Instance: Incomplete Frames

In this paper we argue that an existing theory of concepts called dynamic frame theory, although not developed with that purpose in mind, allows for the precise formulation of a number of problems associated with induction from a single instance. A key role is played by the distinction we introduce between complete and incomplete dynamic frames, for incomplete frames seem to be very elegant candidates for the format of the background knowledge used in induction from a single instance. Furthermore, we show how dynamic frame theory provides the terminology to discuss the justification and the fallibility of incomplete frames. In the Appendix, we give a formal account of incomplete frames and the way these lead to induction from a single instance.