CiteSeerX Scientific Literature Digital Library and Search Engine
(3,645,209 recursos)
CiteSeerX is a scientific literature digital library and search engine that focuses primarily on the literature in computer and information science. CiteSeerx aims to improve the dissemination of scientific literature and to provide improvements in functionality, usability, availability, cost, comprehensiveness, efficiency, and timeliness in the access of scientific and scholarly knowledge

Mostrando recursos 1 - 20 de 3,454,903

1.
h-Monotonically Computable Real Numbers - Xizhong Zheng; Robert Rettinger; George Barmpalias
Let h: N → Q be a computable function. A real number x is called h-monotonically computable (h-mc, for short) if there is a computable sequence (xs) of rational numbers which converges to x h-monotonically in the sense that h(n)|x − xn | ≥ |x − xm | for all n and m> n. In this paper we investigate classes h-MC of h-mc real numbers for different computable functions h. Especially, for computable functions h: N → (0, 1)Q, we show that the class h-MC coincides with the classes of computable and semi-computable real numbers if and only if �...

2.
Effective Jordan Decomposition - Xizhong Zheng; Robert Rettinger
The Jordan decomposition Theorem says that any real function of bounded variation can be expressed as a difference of two increasing functions. This paper investigates the effective version of Jordan decomposition and discusses the properties of variation of computable real functions. First we show that the effective version of Jordan decomposition does not hold in general. Then we give a sufficient and necessary condition for computable real functions of bounded variation which have an effective Jordan decomposition. Applying this condition, we construct a computable real function which has a computable modulus of absolute continuity (hence of bounded variation) but is...

4.
Finite-State Dimension and Real Arithmetic - David Doty, et al.
We use entropy rates and Schur concavity to prove that, for every integer k ≥ 2, every nonzero rational number q, and every real number α, the base-k expansions of α, q + α, and qα all have the same finite-state dimension and the same finitestate strong dimension. This extends, and gives a new proof of, Wall’s 1949 theorem stating that the sum or product of a nonzero rational number and a Borel normal number is always Borel normal.

5.
On the Turing degrees of weakly computable real numbers - Xizhong Zheng
The Turing degree of a real number x is defined as the Turing degree of its binary expansion. This definition is quite natural and robust. In this paper we discuss some basic degree properties of semi-computable and weakly computable real numbers introduced by Weihrauch and Zheng [19]. Among others we show that, there are two real numbers of c.e. binary expansions such that their difference does not have an ω.c.e. Turing degree.

6.
Specker Sequences Revisited - Jakob Grue Simonsen
Specker sequences are constructive, increasing, bounded sequences of rationals that do not converge to any constructive real. A sequence is said to be a strong Specker sequence if it is Specker and eventually bounded away from every constructive real. Within Bishop’s constructive mathematics we investigate non-decreasing, bounded sequences of rationals that eventually avoid sets that are unions of (countable) sequences of intervals with rational endpoints. This yields surprisingly straightforward proofs of certain basic results from constructive mathematics. Within Russian constructivism, we show how to use this general method to generate Specker sequences. Furthermore, we show that any nonvoid subset of...

8.
Zeta-Dimension - David Doty; Xiaoyang Gu; Jack H. Lutz; Elvira Mayordomo; Philippe Moser
where The zeta-dimension of a set A of positive integers is Dimζ(A) = inf{s | ζA(s) < ∞}, ζA(s) = � n −s. Zeta-dimension serves as a fractal dimension on Z + that extends naturally and usefully to discrete lattices such as Z d, where d is a positive integer. This paper reviews the origins of zeta-dimension (which date to the eighteenth and nineteenth centuries) and develops its basic theory, with particular attention to its relationship with algorithmic information theory. New results presented include a gale characterization of zeta-dimension and a theorem on the zeta-dimensions of pointwise sums and products...

9.
Effectively Absolute Continuity and Effective Jordan Decomposability - Xizhong Zheng; Robert Rettinger; Burchard von Braunmühl
Classically, any absolute continuous real function is of bounded variation and hence can always be expressed as a difference of two increasing continuous functions (socalled Jordan decomposition). The effective version of this result is not true. In this paper we give a sufficient and necessary condition for computable real functions which can be expressed as two computable increasing functions (effectively Jordan decomposable, or EJD for short). Using this condition, we prove further that there is a computable real function which has a computable modulus of absolute continuity but is not EJD. The polynomial time version of this result holds accordingly...

10.
On the Hierarchy of ∆ 0 2-Real Numbers - Xizhong Zheng
A real number x is called ∆0 2 if its binary expansion corresponds to a ∆02-set of natural numbers. Such reals are just the limits of computable sequences of rational numbers and hence also called computably approximable. Depending on how fast the sequences converge, ∆0 2-reals have different levels of effectiveness. This leads to various hierarchies of ∆0 2 reals. In this paper we summarize several recent developments related to such kind of hierarchies.

11.
Pushdown Compression - Pilar Albert; Elvira Mayordomo; Philippe Moser; Sylvain Perifel
The pressing need for efficient compression schemes for XML documents has recently been focused on stack computation [6, 9], and in particular calls for a formulation of information-lossless stack or pushdown compressors that allows a formal analysis of their performance and a more ambitious use of the stack in XML compression, where so far it is mainly connected to parsing mechanisms. In this paper we introduce the model of pushdown compressor, based on pushdown transducers that compute a single injective function while keeping the widest generality regarding stack computation. The celebrated Lempel-Ziv algorithm LZ78 [10] was introduced as a general...

12.
On the Hierarchy of ∆ 0 2-Real Numbers - Xizhong Zheng
A real number x is called ∆0 2 if its binary expansion corresponds to a ∆02-set of natural numbers. Such reals are just the limits of computable sequences of rational numbers and hence also called computably approximable. Depending on how fast the sequences converge, ∆0 2-reals have different levels of effectiveness. This leads to various hierarchies of ∆0 2 reals. In this paper we summarize several recent developments related to such kind of hierarchies.

13.
The Arithmetical Complexity of Dimension and Randomness - John M. Hitchcock, et al.
Constructive dimension and constructive strong dimension are effectivizations of the Hausdorff and packing dimensions, respectively. Each infinite binary sequence A is assigned a dimension dim(A) ∈ [0, 1] and a strong dimension Dim(A) ∈ [0, 1]. Let DIM α and DIM α str be the classes of all sequences of dimension α and of strong dimension α, respectively. We show that DIM 0 is properly Π0 2, and that for all ∆02-computable α ∈ (0, 1], DIM α is properly Π0 3. To classify the strong dimension classes, we use a more powerful effective Borel hierarchy where a co-enumerable predicate...

17.
Consistency of random forests and other averaging classifiers - Gérard Biau; Luc Devroye; Gábor Lugosi
This paper is dedicated to the memory of Leo Breiman. In the last years of his life, Leo Breiman promoted random forests for use in classification. He suggested using averaging as a means

19.
Zeta-Dimension (Preliminary Version) - David Doty; Xiaoyang Gu; Jack H. Lutz; Elvira Mayordomo; Philippe Moser
The zeta-dimension of a set A of positive integers is where Dimζ(A) = inf{s | ζA(s) < ∞}, ζA(s) = � n −s. n∈A Zeta-dimension serves as a fractal dimension on Z + that extends naturally and usefully to discrete lattices such as Z d, where d is a positive integer. This paper reviews the origins of zeta-dimension (which date to the eighteenth and nineteenth centuries) and develops its basic theory, with particular attention to its relationship with algorithmic information theory. New results presented include a gale characterization of zeta-dimension and a theorem on the zeta-dimensions of pointwise sums and...

20.
RELATIVIZING CHAITIN’S HALTING PROBABILITY - Rod Downey; Denis R. Hirschfeldt; Joseph S. Miller; ANDRÉ NIES
As a natural example of a 1-random real, Chaitin proposed the halting probability Ω of a universal prefix-free machine. We can relativize this example by considering a universal prefix-free oracle machine U.LetΩA U be the halting probability of UA; this gives a natural uniform way of producing an A-random real for every A ∈ 2ω. It is this operator which is our primary object of study. We can draw an analogy between the jump operator from computability theory and this Omega operator. But unlike the jump, which is invariant (up to computable permutation) under the choice of an effective enumeration...