Search

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]

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: 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: 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]