Search

Program extraction from proofs can be used to obtain verified algorithms in exact real arithmetic for e.g., the signed-digit code representation. In Minlog this has been done in the past with the use of certain coinductive predicates. In a next step we want to analyze the lookahead of these extracted programs. Doing it by hand is quite cumbersome, so instead we change our definition. Instead of a coinductive predicate we use an inductive predicate for the representation of reals that already incorporates the lookahead. In this way the lookahead becomes part of the specification which is carried through all the proofs. In the end we extract programs for computations on a signed-digit representation and we can just read off the lookahead from the specification. • We use the theory TCF for extracting verified algorithms for exact real number arithmetic based on stream representations. • The lookahead of the stream-transformers is explicitly part of the specification. • We use an explicit representation of real numbers rather than an axiomatization of abstract real numbers. [ABSTRACT FROM AUTHOR]

Emerging wireless and mobile applications, such as border intrusion detection with station-based drones, brought a new barrier coverage problem of using sink-based mobile sensors to cover a given line barrier with minimum energy consumption. In this paper, we focus on the uniform sink-based line barrier coverage (SLBC) problem, in which we are given a line barrier and k sink stations distributed on the plane which can emit an infinite number of sensors with an identical sensing radius. The problem aims to find their final positions on the barrier for the sensors emitted by the stations, such that the total moving distance of the sensors is minimized and each point of the barrier is within the sensing area of at least one sensor. We first observe the geometric structure of an optimal solution that any optimal solution can be considered as a set of intersecting tangent (disk) segments, where a tangent (disk) segment is a sequence of tangent disks. Then, we devise an algorithm to calculate all possible tangent (disk) segments and another algorithm to calculate the near-optimal positions for each of such segments. After computing all tangent (disk) segments and their near-optimal positions, an algorithm is proposed to transform uniform SLBC into an instance of the shortest path problem. It is shown the whole algorithm deserves a runtime O (k 2 log ⁡ k r ε) and consumes at most ε more movement than an optimal solution, where ε is any given positive real number, and r and k are the sensor radius and the number of sink stations, respectively. • The algorithm consumes a runtime O (k 2 log ⁡ k r ε) and produces a solution with at most ε more movement than that of an optimum solution. • With the runtime and the performance guarantee, the proposed algorithm behaves in a manner similar to a polynomial-time exact algorithm. • We proved several geometric properties of an optimum solution, which might have possible applications in other variants of the problem. [ABSTRACT FROM AUTHOR]

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]

In this work, we study a range of constrained versions of the k-supplier and k-center problems. In the classical (unconstrained) k -supplier problem, we are given a set of clients C in a metric space X , with distance function d (. ,.). We are also given a set of feasible facility locations L ⊆ X. The goal is to open a set F of k facilities in L to minimize the maximum distance of any client to the closest open facility, i.e., minimize, cost (F , C) ≡ max j ∈ C ⁡ { d (F , j) } , where d (F , j) is the distance of client j to the closest facility in F. The k -center problem is a special case of the k -supplier problem where L = C. We study various constrained versions of the k -supplier problem such as: capacitated , fault-tolerant , ℓ -diversity, etc. These problems fall under a broad framework of constrained clustering. A unified framework for constrained clustering was proposed by Ding and Xu [Algorithmica 2020] in the context of the k -median and k -means objectives. We extend this framework to the k -supplier and k -center objectives in this work. This unified framework allows us to obtain results simultaneously for the following constrained versions of the k -supplier problem: r-gather, r-capacity, balanced, chromatic, fault-tolerant, strongly private, ℓ-diversity, and fair k-supplier problems, with and without outliers. We design Fixed-Parameter Tractable (FPT) algorithms for these problems. FPT algorithms have polynomial running time if the parameter under consideration is a constant. This may be relevant even to a practitioner since the parameter k is a small number in many real clustering scenarios. We obtain the following results: • We give 3 and 2 approximation algorithms for the constrained k -supplier and k -center problems, respectively, with FPT running time k O (k) ⋅ n O (1) , where n = | C ∪ L |. Moreover, these approximation guarantees are tight; that is, for any constant ε > 0 , no algorithm can achieve (3 − ε) and (2 − ε) approximation guarantees for the constrained k -supplier and k -center problems in FPT time, assuming FPT ≠ W [ 2 ]. • We study the constrained clustering problem with outliers. Our algorithm gives 3 and 2 approximation guarantees for the constrained outlier k -supplier and k -center problems, respectively, with FPT running time (k + m) O (k) ⋅ n O (1) , where n = | C ∪ L | and m is the number of outliers. • Our techniques generalise for distance function d (. ,.) z. That is, for any positive real number z , if the cost of a client is defined by d (. ,.) z instead of d (. ,.) , then our algorithm gives 3 z and 2 z approximation guarantees for the constrained k -supplier and k -center problems, respectively. • We design 3 approximation algorithm for a wide range of constrained k -supplier problems with FPT running time f (k). p o l y (n). • We design 2 approximation algorithm for a range of constrained k -center problems with FPT running time f (k). p o l y (n). • We extend the algorithm to outlier setting with FPT running time f (k , m). p o l y (n) , where m = number of outliers. • We show matching lower bounds for the constrained k -supplier and k -center problems in the outlier and non-outlier settings. [ABSTRACT FROM AUTHOR]

According to the Jordan Decomposition Theorem, for any function f : [ 0 , 1 ] → R of bounded variation there exists a pair of nondecreasing functions f 1 , f 2 : [ 0 , 1 ] → R with f = f 1 − f 2. Such a pair is called a Jordan decomposition of f. Ko (1991) and Zheng and Rettinger (2005) have analyzed computability-theoretic and complexity-theoretic aspects of this theorem. We complement their observations by three new results. One of our results says that there exists a polynomial time computable, absolutely continuous function f : [ 0 , 1 ] → R with polynomial modulus of absolute continuity such that, on the one hand, the so-called standard Jordan decomposition of f is computable but, on the other hand, neither the standard Jordan decomposition of f nor any other Jordan decomposition of f can be computed easily, say, in polynomial time, or in exponential time. • A function with a non-computable standard Jordan decomposition can have a polytime computable Jordan decomposition. • A computable but not polytime computable standard Jordan decomposition allows a polytime computable Jordan decomposition. • There is a PAC function without polytime computable Jordan decomposition but with computable standard Jordan decomposition. [ABSTRACT FROM AUTHOR]

The independent set polynomial is important in many areas of combinatorics, computer science, and statistical physics. For every integer Δ ≥ 2 , the Shearer threshold is the value λ ⁎ (Δ) = (Δ − 1) Δ − 1 / Δ Δ. It is known that for λ < − λ ⁎ (Δ) , there are graphs G with maximum degree Δ whose independent set polynomial, evaluated at λ , is at most 0. Also, there are no such graphs for any λ > − λ ⁎ (Δ). This paper is motivated by the computational problem of approximating the independent set polynomial when λ < − λ ⁎ (Δ). The key issue in complexity bounds for this problem is "implementation". Informally, an implementation of a real number λ ′ is a graph whose hard-core partition function, evaluated at λ , simulates a vertex-weight of λ ′ in the sense that λ ′ is the ratio between the contribution to the partition function from independent sets containing a certain vertex and the contribution from independent sets that do not contain that vertex. Implementations are the cornerstone of intractability results for the problem of approximately evaluating the independent set polynomial. Our main result is that, for any λ < − λ ⁎ (Δ) , it is possible to implement a set of values that is dense over the reals. The result is tight in the sense that it is not possible to implement a set of values that is dense over the reals for any λ > λ ⁎ (Δ). Our result has already been used in a paper with Bezáková (STOC 2018) to show that it is #P-hard to approximate the evaluation of the independent set polynomial on graphs of degree at most Δ at any value λ < − λ ⁎ (Δ). In the appendix, we give an additional incomparable inapproximability result (strengthening the inapproximability bound to an exponential factor, but weakening the hardness to NP-hardness). [ABSTRACT FROM AUTHOR]

In the famous paper in which he introduced what is now known as the Turing machine, Alan Turing gave a definition of computable real numbers under which it turns out that multiplication by 3 is uncomputable. This shortcoming vanished in a Correction to his paper that Turing himself published shortly afterwards, but it clearly illustrates the subtlety of defining computability issues correctly. In this paper, we give the name "printable" to real numbers that Turing originally called "computable", we recall what is now the generally accepted definition of computable real numbers (which is not quite Turing's amended definition, but is equivalent to it), and we contrast the two notions. Despite the fact that the multiplication by 3 of printable numbers is uncomputable, as opposed to the same operation on computable numbers, a real number is computable if and only if it is printable. The resolution of this apparent paradox is that no machine can transform the "computable" description of a real number to its "printable" description, as Turing proved in his Correction. Finally, we address the subtle issue of allowing or not the printable description of a real number to end with an infinite sequence of 9s (or of 1s in binary), which was left open by Turing in his Correction. Several of these results were already known, as they appear in scattered places, some in non-refereed publications, but we give a unified treatment with some different proofs and a historical perspective. • Alan Turing's original definition of computable real numbers was inadequate. • Turing's use of the word Entscheidungsproblem led us to invent the Druckproblem. • The correct definition of computable real numbers is very subtle. • All computable real numbers are printable, but this is inherently non-constructive. • Discontinuous functions of the real numbers on closed intervals are uncomputable. [ABSTRACT FROM AUTHOR]

We study the decomposition of multivariate polynomials as sums of powers of linear forms. As one of our main results, we give a randomized algorithm for the following problem: given a homogeneous polynomial f (x 1 , ... , x n) of degree 3, decide whether it can be written as a sum of cubes of linearly independent linear forms with complex coefficients. Compared to previous algorithms for the same problem, the two main novel features of this algorithm are: (i) It is an algebraic algorithm, i.e., it performs only arithmetic operations and equality tests on the coefficients of the input polynomial f. In particular, it does not make any appeal to polynomial factorization. (ii) For f ∈ Q [ x 1 , ... , x n ] , the algorithm runs in polynomial time when implemented in the bit model of computation. The algorithm relies on methods from linear and multilinear algebra (symmetric tensor decomposition by simultaneous diagonalization). We also give a version of our algorithm for decomposition over the field of real numbers. In this case, the algorithm performs arithmetic operations and comparisons on the input coefficients. Finally we give several related derandomization results on black box polynomial identity testing, the minimization of the number of variables in a polynomial, the computation of Lie algebras and factorization into products of linear forms. [ABSTRACT FROM AUTHOR]

Two robots stand at the origin of the infinite line and are tasked with searching collaboratively for an exit at an unknown location on the line. They can travel at maximum speed b and can change speed or direction at any time. The two robots can communicate with each other at any distance and at any time. The task is completed when the last robot arrives at the exit and evacuates. We study time-energy tradeoffs for the above evacuation problem. The evacuation time is the time it takes the last robot to reach the exit. The energy it takes for a robot to travel a distance x at speed s is measured as x s 2. The total and makespan evacuation energies are respectively the sum and maximum of the energy consumption of the two robots while executing the evacuation algorithm. Assuming that the maximum speed is b , and the evacuation time is at most cd , where d is the distance of the exit from the origin and c is some positive real number, we study the problem of minimizing the total energy consumption of the robots. We prove that the problem is solvable only for b c ≥ 3. For the case b c = 3 , we give an optimal algorithm, and give upper bounds on the energy for the case b c > 3. We also consider the problem of minimizing the evacuation time when the available energy is bounded by Δ. Surprisingly, when Δ is a constant, independent of the distance d of the exit from the origin, we prove that evacuation is possible in time O (d 3 / 2 log ⁡ d) , and this is optimal up to a logarithmic factor. When Δ is linear in d , we give upper bounds on the evacuation time. [ABSTRACT FROM AUTHOR]

We present a uniform method for translating an arbitrary nondeterministic finite automaton (NFA) into a deterministic mass action input/output chemical reaction network (I/O CRN) that simulates it. The I/O CRN receives its input as a continuous time signal consisting of concentrations of chemical species that vary to represent the NFA's input string in a natural way. The I/O CRN exploits the inherent parallelism of chemical kinetics to simulate the NFA in real time with a number of chemical species that is linear in the size of the NFA. We prove that the simulation is correct and that it is robust with respect to perturbations of the input signal, the initial concentrations of species, the output (decision), and the rate constants of the reactions of the I/O CRN. [ABSTRACT FROM AUTHOR]

Top- k query processing is an important building block for ranked retrieval, with various applications. In this paper, we consider two interesting top- k retrieval problems. In the first problem, we consider the r -combinations of a set S of n real numbers. Precisely, on any input set S , any positive integers k and r , our target is to generate the k best size- r subsets of S efficiently, whose sum of elements is maximized. Our method defines a novel metadata structure G for n and r , even before S and k are known, so that we can later use G to report the top- k r -combinations efficiently when S is available. In the second problem, we consider the top- k procurement decision problem in a multi-item auction, where the input consists of (i) a set of items, where each item is partitioned into equal number of shares, (ii) a set of suppliers, and (iii) for each supplier, her prices of selling different shares of each item; our target is to find k procurements with the least total costs. Our solution extends the novel metadata structure G of the first problem to speed up the reporting steps. For both of the above problems, we further show that the metadata structure can be generated on the fly, thereby saving a considerable amount of storage space. [ABSTRACT FROM AUTHOR]

We extend the framework for complexity of operators in analysis devised by Kawamura and Cook (2012) to allow for the treatment of a wider class of representations. The main novelty is to endow represented spaces of interest with an additional function on names, called a parameter, which measures the complexity of a given name. This parameter generalises the size function which is usually used in second-order complexity theory and therefore also central to the framework of Kawamura and Cook. The complexity of an algorithm is measured in terms of its running time as a second-order function in the parameter, as well as in terms of how much it increases the complexity of a given name, as measured by the parameters on the input and output side. As an application we develop a rigorous computational complexity theory for interval computation. In the framework of Kawamura and Cook the representation of real numbers based on nested interval enclosures does not yield a reasonable complexity theory. In our new framework this representation is polytime equivalent to the usual Cauchy representation based on dyadic rational approximation. By contrast, the representation of continuous real functions based on interval enclosures is strictly smaller in the polytime reducibility lattice than the usual representation, which encodes a modulus of continuity. Furthermore, the function space representation based on interval enclosures is optimal in the sense that it contains the minimal amount of information amongst those representations which render evaluation polytime computable. [ABSTRACT FROM AUTHOR]

We introduce a new variant of the game of Cops and Robbers played on graphs, where the robber is invisible unless outside the neighbor set of a cop. The hyperopic cop number is the corresponding analogue of the cop number, and we investigate bounds and other properties of this parameter. We characterize the cop-win graphs for this variant, along with graphs with the largest possible hyperopic cop number. We analyze the cases of graphs with diameter 2 or at least 3, focusing on when the hyperopic cop number is at most one greater than the cop number. We show that for planar graphs, as with the usual cop number, the hyperopic cop number is at most 3. The hyperopic cop number is considered for countable graphs, and it is shown that for connected chains of graphs, the hyperopic cop density can be any real number in [ 0 , 1 / 2 ]. [ABSTRACT FROM AUTHOR]

A graph G = (V , E) is a pairwise compatibility graph (PCG) if there exists an edge-weighted tree T and two non-negative real numbers d m i n and d m a x , d m i n ≤ d m a x , such that each node u ∈ V is uniquely associated to a leaf of T and there is an edge (u , v) ∈ E if and only if d m i n ≤ d T (u , v) ≤ d m a x , where d T (u , v) is the sum of the weights of the edges on the unique path P T (u , v) from u to v in T. Understanding which graph classes lie inside and which ones outside the PCG class is an important issue. In this paper we show that some interesting classes of graphs have empty intersection with PCG; they are wheels, strong product of a cycle and P 2 and the square of an n node cycle, with n sufficiently large. As a side effect, we show that the smallest planar graph not to be PCG has not 20 nodes, as previously known, but only 8 (it is C 8 2). [ABSTRACT FROM AUTHOR]

ksmt is a CDCL-style calculus for solving non-linear constraints over the real numbers involving polynomials and transcendental functions. In this article we investigate properties of the ksmt calculus and show that it is a δ -complete decision procedure for bounded problems. For that purpose we provide concrete algorithms computing linearisations based on either uniform or local moduli of continuity of non-linear functions. The latter method is called local linearisation and is shown to have desirable properties sufficient for termination and which also allow for more efficient treatment of non-linear constraints. Our methods for constructing linearisations are based on computable analysis, in particular we introduce the Cauchy-compatible compact representation of reals and prove its names to be locally compact, allowing for more efficient computation of local linearisations while maintaining δ -completeness. • ksmt is a CDCL-style calculus for solving nonlinear constraints over real numbers involving polynomials and transcendentals. • We show properties of the calculus itself and that it is a δ -complete decision procedure for bounded problems. • Concrete algorithms computing linearisations based on uniform and local moduli of continuity of the non-linear function. • Local linearisations have desirable properties for termination and they allow efficient treatment of nonlinear constraints. • Linearisations based on methods from computable analysis, as is the CCC representation of reals with locally compact names. [ABSTRACT FROM AUTHOR]

Spiking neural P systems (SN P systems) are bio-inspired neural-like computational devices that mimic the communication between two nearby neurons and the spike changes in the neuron. This study incorporates concepts of the weight of synapses and the delay on synapses to increase the bio-explainability (the model can better simulate the communication between neurons), where the weight is a natural feature of synapses, and the delay is that in the communication between neurons, through synapses. Thus, an innovative type of spiking neural-like P system is defined, called spiking neural P systems with weights and delays on synapses (W D S N P systems). In W D S N P systems, synapses are assigned weights and delays, where weights are real numbers and delays are natural numbers. Results proved in this paper show that W D S N P systems can reach Turing universality in the generating and accepting mode. The semi-uniform solution for the Subset Sum problem demonstrates that W D S N P systems can solve NP -complete problems efficiently. [ABSTRACT FROM AUTHOR]

Abstract The Toffoli gate and the Hadamard gate give rise to an approximately universal set of quantum computational gates. We study the algebraic properties of extensions of this system by introducing the notion of the extended Shi–Aharonov structure. The quotient of this structure is isomorphic to a structure based on a particular set of real numbers (the Bloch hypersphere). The aim of this paper is to bring together researchers working in different areas (quantum circuits, algebra, geometry) opening up new perspectives. The algebraic approach may be useful in circuit analysis. [ABSTRACT FROM AUTHOR]

The 1.5D terrain guarding problem examines a 1.5D terrain as an x -monotone polygonal chain in a plane to find the minimum guarding set for a given input terrain. This problem is NP-complete. In real world applications, guard power is limited and can only cover things within a range. Considering this limitation, the present study introduces the “ terrain guard range ” as a new geometric parameter by discretizing the definition of range, then presents a fixed-parameter algorithm to demonstrate that the 1.5D terrain guarding problem is fixed-parameter tractable with respect to the introduced parameter. [ABSTRACT FROM AUTHOR]

The maximal sum of a sequence A of n real numbers is the greatest sum of all elements of any linearly contiguous and possibly empty subsequence of A . It can be computed in O ( n ) time by means of Kadane's algorithm. Letting A ( x → p ) denote the sequence which results from inserting a real number x just after element A [ p − 1 ] , we show how the maximal sum of A ( x → p ) can be computed in O ( 1 ) worst-case time for any given x and p , provided that an O ( n ) time preprocessing step has already been executed on A . In particular, this implies that, given m pairs ( x 0 , p 0 ) , … , ( x m − 1 , p m − 1 ) , we can compute the maximal sums of sequences A ( x 0 → p 0 ) , … , A ( x m − 1 → p m − 1 ) optimally in O ( n + m ) time, improving on the straightforward and suboptimal strategy of applying Kadane's algorithm to each sequence A ( x i → p i ) , which takes a total of Θ ( n m ) time. We also show that the same time bound is attainable when circular subsequences of A ( x → p ) are taken into account. Our algorithms are easy to implement in practice, and they were motivated by a buffer minimization problem on wireless mesh networks. [ABSTRACT FROM AUTHOR]

Define ‖ n ‖ to be the complexity of n , the smallest number of ones needed to write n using an arbitrary combination of addition and multiplication. John Selfridge showed that ‖ n ‖ ≥ 3 log 3 ⁡ n for all n . Based on this, this author and Zelinsky defined [4] the “defect” of n , δ ( n ) : = ‖ n ‖ − 3 log 3 ⁡ n , and this author showed that the set of all defects is a well-ordered subset of the real numbers [1] . This was accomplished by showing that for a fixed real number s , there is a finite set S of polynomials called “low-defect polynomials” such that for any n with δ ( n ) < s , n has the form f ( 3 k 1 , … , 3 k r ) 3 k r + 1 for some f ∈ S . However, using the polynomials produced by this method, many extraneous n with δ ( n ) ≥ s would also be represented. In this paper we show how to remedy this and modify S so as to represent precisely the n with δ ( n ) < s and remove anything extraneous. Since the same polynomial can represent both n with δ ( n ) < s and n with δ ( n ) ≥ s , this is not a matter of simply excising the appropriate polynomials, but requires “truncating” the polynomials to form new ones. [ABSTRACT FROM AUTHOR]

In this paper we investigate the computational complexity of solving ordinary differential equations (ODEs) y ′ = p ( y ) over unbounded time domains , where p is a vector of polynomials. Contrarily to the bounded (compact) time case, this problem has not been well-studied, apparently due to the “intuition” that it can always be reduced to the bounded case by using rescaling techniques. However, as we show in this paper, rescaling techniques do not seem to provide meaningful insights on the complexity of this problem, since the use of such techniques introduces a dependence on parameters which are hard to compute. We present algorithms which numerically solve these ODEs over unbounded time domains. These algorithms have guaranteed accuracy, i.e. given some arbitrarily large time t and error bound ε as input, they will output a value y ˜ which satisfies ‖ y ( t ) − y ˜ ‖ ≤ ε . We analyze the complexity of these algorithms and show that they compute y ˜ in time polynomial in several quantities including the time t , the accuracy of the output ε and the length of the curve y from 0 to t , assuming it exists until time t . We consider both algebraic complexity and bit complexity. [ABSTRACT FROM AUTHOR]

We elaborate a recursion-theoretic method to define real numbers which are random to any jump of the halting problem. This is obtained by generalizing a result of V. Becher and G. Chaitin dealing with the class of cofinite sets. As in the work of V. Becher and S. Grigorieff (but this time in the context of open sets in Cantor space) appeal to completeness phenomena replaces machine arguments. [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: The recurrence function of an infinite word w was introduced by Morse and Hedlund in relation to symbolic dynamics. It is the size of the smallest window such that, wherever its position on w, all length n subwords of w will appear at least once inside that window. The recurrence quotient of w, defined as , is useful for studying the growth rate of . It is known that if w is periodic, then , while if w is not, then . A long standing conjecture from Rauzy states that the latter can be improved to , this bound being true for each Sturmian word and being reached by the Fibonacci word. In this paper, we study in particular the spectrum of values taken by the recurrence quotients of infinite partial words, which are sequences that may have some undefined positions. In this case, we determine exactly the spectrum of values, which turns out to be 1, every real number greater than or equal to 2, and ∞. More precisely, if an infinite partial word w is “ultimately factor periodic”, then , while if w is not, then , and we give constructions of infinite partial words achieving each value. [Copyright &y& Elsevier]

Abstract: We give an elementary and direct proof of the following theorem: A real number is normal to a given integer base if, and only if, its expansion in that base is incompressible by lossless finite-state compressors (these are finite automata augmented with an output transition function such that the automata input–output behaviour is injective; they are also known as injective finite-state transducers). As a corollary we obtain V.N. Agafonov’s theorem on the preservation of normality on subsequences selected by finite automata. [Copyright &y& Elsevier]

Abstract: We study, in this paper, the relationship among the classes of logarithmic-space computable real numbers under different representations. We consider logarithmic-space computable real numbers under the Cauchy function representation, the general left cut representation, the standard left cut representation, and the binary expansion representation. It is shown that the relationship among these classes of real numbers depends on the relationship between the discrete complexity classes and , the classes of tally sets in and , respectively. First, if , then the relationship among the four classes of logarithmic-space computable real numbers is the same as that among these classes of polynomial-time computable real numbers. On the other hand, if , then we get different relationships from those among classes of polynomial-time computable real numbers. For instance, while the classes of polynomial-time computable real numbers under the general left cut and the Cauchy function representations are equivalent, we show, under the assumption of , that the class of logarithmic-space computable real numbers under the general left cut representation properly contains the class of logarithmic-space computable real numbers under the Cauchy function representation. In addition, if , then the two classes of logarithmic-space computable real numbers under the standard left cut and the Cauchy function representations are incomparable. [Copyright &y& Elsevier]

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: In this paper, we solve the problem of determining a consistent instantiation of any finite, path-consistent and atomic network of base relations. We already know that such networks that contain a finite number of variables have a realization in any dimension . The novelty of our work is that given any path-consistent and atomic constraint network, we are able to construct in polynomial time a realization that satisfies it. For this purpose, we suitably instantiate the variables of such a network by associating to them some regular closed sets of the set of real numbers. [Copyright &y& Elsevier]

Abstract: We study the derivational complexities of string rewriting systems. We discuss the following fundamental question: which functions can be derivational complexities of terminating finite string rewriting systems? They are recursive, but for any recursive function, there is a derivational complexity larger than it. We relate them to the time functions of Turing machines. In particular, we show that the functions and for a real number are equivalent to the derivational complexity of some finite string rewriting systems if the computational complexity of is relatively low (for example, is rational, algebraic, or ). On the other hand, they cannot be equivalent to any derivational complexities if the complexity of is high. [Copyright &y& Elsevier]

Abstract: Given a univariate complex polynomial and a closed complex domain , whose boundary is a curve parameterized by a piecewise rational function, we propose two computational algorithms for finding a univariate complex polynomial such that has a zero in and the distance between and is minimal. Our approach is composed of two steps. First, in the case of consisting of one point , we give explicit formulas of and the minimal distance in terms of . Next, the case of a general closed domain is considered by using the property that a nearest polynomial has a zero on the boundary . The curve is parameterized piecewisely, and on each piece we search for the minimum of the distance between and . At this step we exploit the explicit formula of the minimal distance as a function of a point . Then the global minimum and the nearest polynomial are obtained by comparing the piecewise minima. Some examples are presented: one of them confirms that the distance between a nearest complex polynomial and a given polynomial is less than that between a nearest real polynomial and the given polynomial. [Copyright &y& Elsevier]

Abstract: This paper studies directional dynamics on one-dimensional cellular automata, a formalism previously introduced by the third author. The central idea is to study the dynamical behavior of a cellular automaton through the conjoint action of its global rule (temporal action) and the shift map (spacial action): qualitative behaviors inherited from topological dynamics (equicontinuity, sensitivity, expansivity) are thus considered along arbitrary curves in space–time. The main contributions of the paper concern equicontinuous dynamics which can be connected to the notion of consequences of a word. We show that there is a cellular automaton with an equicontinuous dynamics along a parabola, but which is sensitive along any linear direction. We also show that real numbers that occur as the slope of a limit linear direction with equicontinuous dynamics in some cellular automaton are exactly the computably enumerable numbers. [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: Given a sequence of real numbers and a positive integer , the Sum Selection Problem is to find the segment such that the rank of the sum is over all segments. We present a deterministic algorithm for this problem that runs in time. The previously best known result for this problem is a randomized algorithm that runs in expected time. Applying this algorithm we can obtain a deterministic algorithm for the k Maximum Sums Problem, i.e., the problem of enumerating the largest sum segments, that runs in time. The previously best known randomized and deterministic algorithms for the k Maximum Sums Problem run respectively in expected time and in worst case time. [Copyright &y& Elsevier]

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: Sturmian sequences appear in the work of Markoff on approximations of real numbers and minima of quadratic functions. In particular, Christoffel words, or equivalently pairs of relatively prime nonnegative integers, parametrize the Markoff numbers. It was asked by Frobenius if this parametrization is injective. We answer this conjecture for a particular subclass of these numbers, and show that a special Sturmian sequence of irrational slope determines the order of the Markoff numbers in this subclass. [Copyright &y& Elsevier]

Abstract: This article studies the expressive power of finite-state automata recognizing sets of real numbers encoded positionally. It is known that the sets that are definable in the first-order additive theory of real and integer variables can all be recognized by weak deterministic Büchi automata, regardless of the encoding base . In this article, we prove the reciprocal property, i.e., a subset of that is recognizable by weak deterministic automata in every base is necessarily definable in . This result generalizes to real numbers the well-known Cobham’s theorem on the finite-state recognizability of sets of integers. Our proof gives interesting insight into the internal structure of automata recognizing sets of real numbers, which may lead to efficient data structures for handling these sets. [Copyright &y& Elsevier]

Abstract: In this paper we study optimization problems with verifiable one-parameter selfish agents introduced by Auletta et al. [V. Auletta, R. De Prisco, P. Penna, P. Persiano, The power of verification for one-parameter agents, in: Proceedings of the 31st International Colloquium on Automata, Languages and Programming, ICALP, in: LNCS, vol. 3142, 2004, pp. 171–182]. Our goal is to allocate load among the agents, provided that the secret data of each agent is a single positive real number: the cost they incur per unit load. In such a setting the payment is given after the load completion, therefore if a positive load is assigned to an agent, we are able to verify if the agent declared to be faster than she actually is. We design truthful mechanisms when the agents’ type sets are upper-bounded by a finite value. We provide a truthful mechanism that is -approximate if the underlying algorithm is -approximate and weakly-monotone. Moreover, if type sets are also discrete, we provide a truthful mechanism preserving the approximation ratio of its algorithmic part. Our results improve the existing ones which provide truthful mechanisms dealing only with finite type sets and do not preserve the approximation ratio of the underlying algorithm. Finally, we give applications for our payment schemes. Firstly, we give a full characterization of the problem by using our techniques. Even if our payment schemes need upper-bounded type sets, every instance of can be “mapped” into an instance with upper-bounded type sets preserving the approximation ratio. In conclusion, we turn our attention to binary demand games. In particular, we show that the Minimum Radius Spanning Tree admits an exact truthful mechanism with verification achieving time (and space) complexity of the fastest centralized algorithm for it. This contrasts with a recent truthful mechanism for the same problem [G. Proietti, P. Widmayer, A truthful mechanism for the non-utilitarian minimum radius spanning tree problem, in: Proceedings of the 17th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA, ACM Press, 2005, pp. 195–202] which pays a linear factor with respect to the complexity of the fastest centralized algorithm. Such a result is extended to several binary demand games studied in literature. [Copyright &y& Elsevier]

We prove that for every real number there exists an infinite word over a finite alphabet such that is the critical exponent of . [Copyright &y& Elsevier]

Abstract: Several results on continued fractions expansions are on indirect consequences of the mirror formula. We survey occurrences of this formula for Sturmian real numbers, for (simultaneous) Diophantine approximation and for formal power series. [Copyright &y& Elsevier]

Abstract: Given a sequence of real numbers and an integer parameter , the problem studied in this paper is to compute subsequences of consecutive elements with the sums of their elements being the largest, the second largest, …, and the th largest among all possible range sums of the input sequence. For any value of , , we design a fast algorithm that takes time in the worst case to compute and rank all such subsequences. We also prove that our algorithm is optimal for by providing a matching lower bound. Moreover, our algorithm is an improvement over the previous results on the maximum sum subsequences problem (where only the subsequences are requested and no ordering with respect to their relative sums will be determined). Furthermore, given the fact that we have computed the th largest sums, our algorithm retrieves the th largest sum in time, after time of preprocessing. [Copyright &y& Elsevier]

Abstract: Let be a sequence of real numbers . We consider the Sum Selection Problem as that of finding the segment such that the rank of over all possible feasible segments is , where a feasible segment is a consecutive subsequence of , and its width satisfies for some given integers and , and . It is a generalization of two well-known problems: the Selection Problem in computer science for which , and the Maximum Sum Segment Problem in bioinformatics for which the rank is the total number of possible feasible segments. We will give a randomized algorithm for the Sum Selection Problem that runs in expected time. It matches the optimal time randomized algorithm for the Selection Problem. We can also solve the k Maximum Sums Problem, to enumerate the largest sums, in expected time. The previously best known result was an algorithm that solves this problem for the case when , and runs in time in the worst case. [Copyright &y& Elsevier]

Abstract: In an unpublished manuscript, Alan Turing gave a computable construction to show that absolutely normal real numbers between 0 and 1 have Lebesgue measure 1; furthermore, he gave an algorithm for computing instances in this set. We complete his manuscript by giving full proofs and correcting minor errors. While doing this, we recreate Turing’s ideas as accurately as possible. One of his original lemmas remained unproved, but we have replaced it with a weaker lemma that still allows us to maintain Turing’s proof idea and obtain his result. [Copyright &y& Elsevier]

Abstract: Suppose is a partially ordered set with the partial order defined by divisibility, that is, for any two elements satisfying divides , we have . A table of real numbers is said to be consistent with , provided that for any two elements satisfying divides , . Given a real number , we want to determine whether , by comparing with as few entries of as possible. In this paper, we investigate the complexity , measured by the number of comparisons, of the above search problem. We present a search algorithm for and prove a lower bound on using an adversary argument. [Copyright &y& Elsevier]

Abstract: To any sequence of real numbers , we can associate another sequence , which Knuth calls its binomial transform. This transform is defined through the rule We study the properties of this transform, obtaining rules for its manipulation and a table of transforms, that allow us to invert many transforms by inspection. We use these methods to perform a detailed analysis of skip lists, a probabilistic data structure introduced by Pugh as an alternative to balanced trees. In particular, we obtain the mean and variance for the cost of searching for the first or the last element in the list (confirming results obtained previously by other methods), and also for the cost of searching for a random element (whose variance was not known). We obtain exact solutions, although not always in closed form. From them we are able to find the corresponding asymptotic expressions. [Copyright &y& Elsevier]

Abstract: We implement exact real numbers in the logical framework Coq using streams, i.e., infinite sequences, of digits, and characterize constructive real numbers through a minimal axiomatization. We prove that our construction inhabits the axiomatization, working formally with coinductive types and corecursive proofs. Thus we obtain reliable, corecursive algorithms for computing on real numbers. [Copyright &y& Elsevier]

Abstract: I discuss the design and performance issues arising in the efficient implementation of the scaled-integer exact real arithmetic model introduced by Boehm and others. This system represents a real number with a automatically controlled level of precision by a rational with implicit denominator. I describe three practical codes, in python, C and C. These allow the convenient use of this computational paradigm in commonly used imperative languages. [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]