Search

This paper enriches a pre-existing decision algorithm, which in turn augmented a fragment of Tarski's elementary algebra with one-argument real functions endowed with a continuous first derivative. In its present (still quantifier-free) version, our decidable language embodies the addition of functions and multiplication of functions by scalars; the issue we address is the one of satisfiability. As regards real numbers, individual variables and constructs designating the basic arithmetic operations are available, along with comparison relators. As regards functions, we have variables of another sort, out of which compound terms are formed by means of constructs designating addition and differentiation. An array of predicates designates various relationships between functions, as well as function properties, that may hold over intervals of the real line; those are: function comparisons, strict and non-strict monotonicity / convexity / concavity, comparisons between the derivative of a function and a real-valued term. Our decision method consists in preprocessing the given formula into an equi-satisfiable quantifier-free formula of the elementary algebra of real numbers, whose satisfiability can then be checked by means of Tarski's decision method. No direct reference to functions will appear in the target formula, each function variable having been superseded by a collection of stub real variables; hence, in order to prove that the proposed translation is satisfiability-preserving, we must figure out a flexible-enough family of interpolating C 1 functions that can accommodate a model for the source formula whenever the target formula turns out to be satisfiable. With respect to the results announced in earlier papers of the same stream, a significant effort went into designing the family of interpolating functions so that it could meet the new constraints stemming from the presence of function addition (along with differentiation) among the constructs of our fragment of mathematical analysis. • A formal language RDF* concerned with differentiable real functions is proposed. • The class of differentiable functions treated is closed under addition. • The expressive power of RDF* is illustrated through a gallery of examples. • A satisfiability-preserving algorithm reducing RDF* formulas into an existential sentence of Tarskian algebra is presented. • The correctness of the reduction algorithm is reported. [ABSTRACT FROM AUTHOR]

The Dilworth number of a graph is the size of the largest subset of its nodes in which the close neighborhood of no node contains the neighborhood of another one. In this paper we give a new characterization of Dilworth k graphs, for each value of k, exactly defining their structure. Moreover, we put these graphs in relation with pairwise compatibility graphs (PCGs), i.e. graphs on n nodes that can be generated from an edge-weighted tree T that has n leaves, each representing a different node of the graph; two nodes are adjacent in the graph if and only if the weighted distance between the corresponding leaves in T is contained between two given non-negative real numbers, m and M. When either m or M are not used to eliminate edges from G, the two subclasses leaf power and minimum leaf power graphs (LPGs and mLPGs, respectively) are defined. Here we prove that graphs that are either LPGs or mLPGs of trees obtained connecting the centers of k stars with a path are Dilworth k graphs, and the opposite is true when k=1,2, but not when k≥3. Finally, we show that the relations we proved between Dilworth k graphs and chains of k stars hold only for LPGs and mLPGs, but not for PCGs. [ABSTRACT FROM AUTHOR]

The Dilworth number of a graph is the size of the largest subset of its nodes in which the close neighborhood of no node contains the neighborhood of another one. In this paper we give a new characterization of Dilworth k graphs, for each value of k, exactly defining their structure. Moreover, we put these graphs in relation with pairwise compatibility graphs (PCGs), i.e. graphs on n nodes that can be generated from an edge-weighted tree T that has n leaves, each representing a different node of the graph; two nodes are adjacent in the graph if and only if the weighted distance between the corresponding leaves in T is contained between two given non-negative real numbers, m and M. When either m or M are not used to eliminate edges from G, the two subclasses leaf power and minimum leaf power graphs (LPGs and mLPGs, respectively) are defined. Here we prove that graphs that are either LPGs or mLPGs of trees obtained connecting the centers of k stars with a path are Dilworth k graphs, and the opposite is true when k=1,2, but not when k≥3. Finally, we show that the relations we proved between Dilworth k graphs and chains of k stars hold only for LPGs and mLPGs, but not for PCGs. [ABSTRACT FROM AUTHOR]

Abstract: A graph is called a pairwise compatibility graph (PCG) if there exists a tree , a positive edge weight function on , and two non-negative real numbers , such that each leaf of corresponds to a vertex and there is an edge if and only if where is the sum of the weights of the edges on the unique path from to in . In this paper we analyze the class of PCGs in relation to two particular subclasses resulting from the cases where the constraints on the distance between the pairs of leaves concern only (LPG) or only (mLPG). In particular, we show that the union of LPG and mLPG classes does not coincide with the whole class of PCGs, their intersection is not empty, and that neither of the classes LPG and mLPG is contained in the other. Finally, we study the closure properties of the classes PCG, mLPG and LPG, under some common graph operations. In particular, we consider the following operations: adding an isolated or universal vertex, adding a pendant vertex, adding a false or a true twin, taking the complement of a graph and taking the disjoint union of two graphs. [Copyright &y& Elsevier]

Abstract: An -labeling of a graph is defined as a function from the vertex set into the nonnegative integers such that for any two vertices , , if and if , where is the distance between and in . The -labeling number of is the smallest number such that has an -labeling with . In this paper, we consider the graph formed by the skew product and converse skew product of two graphs, and give new upper bounds of the -labeling number, which improves the upper bounds obtained by Shao and Zhang [Z.D. Shao, D. Zhang, Improved upper bounds on the -labeling of the skew and converse skew product graphs, Theoret. Comput. Sci. 400 (2008) 230–233] in many cases. [Copyright &y& Elsevier]

Abstract: Let be the number of -words of length . Say that a -word is left doubly extendable (LDE) if both and are . We show that for any positive real number and positive integer such that the proportion of 2’s is greater than in each LDE word of length exceeding , there are positive constants and such that for all positive integers . With the best value known for , and large , this gives [ABSTRACT FROM AUTHOR]

Abstract: Let the (subword) complexity of a sequence over a finite set be the function , where denotes the number of distinct blocks of size in . In this paper, we study the complexity of when each , , is a -automatic sequence over a finite set and are pairwise coprime integers. As an application, we answer a question of Allouche and Shallit regarding morphic real numbers. [Copyright &y& Elsevier]

Abstract: A real number x is said to be effective if there exists an algorithm which, given a required tolerance , returns a binary approximation for x with . Effective real numbers are interesting in areas of numerical analysis where numerical instability is a major problem. One key problem with effective real numbers is to perform intermediate computations at the smallest precision which is sufficient to guarantee an exact end-result. In this paper we first review two classical techniques to achieve this: a priori error estimates and interval analysis. We next present two new techniques: “relaxed evaluations” reduce the amount of re-evaluations at larger precisions and “balanced error estimates” automatically provide good tolerances for intermediate computations. [Copyright &y& Elsevier]