29806002
Prefix-Free Languages and Initial Segments of Computably Enumerable Degrees
We study prefix-free presentations of computably enumerable reals. In [2], Calude et. al. proved that a real α is c.e. if and only if there is an infinite, computably enumerable prefix-free set V such that α = Σσ∈V 2-|σ|. Following Downey and LaForte [5], we call V a prefixfree presentation of α. Each computably enumerable real has a computable presentation. Say that a c.e. real α is simple if each presentation of α is computable. Downey and LaForte [5] proved that simple reals locate on every jump class. In this paper, we prove that there is a noncomputable c.e. degree bounding no noncomputable simple reals. Thus, simple reals are not dense in the structure of computably enumerable degrees.
1638130
Bounding computably enumerable degrees in the Ershov hierarchy
Nanyang Technol Univ, Sch Math & Phys Sci, Div Math Sci, Singapore 639798, Singapore. Chinese Acad Sci, Inst Software, Beijing 100080, Peoples R China. Natl Univ Singapore, Dept Math, Singapore 119260, Singapore.
35293254
Quasi-complements of the cappable degrees
Say that a nonzero c. e. degree b is a quasi-complement of a c. e. degree a if a ∩ b = 0 and a ∪ b is high. It is well-known (due to Shore) that each cappable degree has a high quasi-complement. However, by the existence of the almost deep degrees, there are nonzero cappable degrees having no low quasi-complements. In this paper, we prove that any nonzero cappable degree has a low2 quasi-complement. (© 2004 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)
7723209
1-Generic splittings of computably enumerable degrees
Say a set G⊆ω is 1-generic if for any e∈ω, there is a string σ⊂G such that {e}σ(e)↓ or ∀τ⊇σ({e}τ(e)↑). It is known that 0′ can be split into two 1-generic degrees. In this paper, we generalize this and prove that any nonzero computably enumerable degree can be split into two 1-generic degrees. As a corollary, no two computably enumerable degrees bound the same class of 1-generic degrees.
18609322
On the Quotient Structure of Computably Enumerable Degrees Modulo the Noncuppable Ideal
We show that minimal pairs exist in the quotient structure of $\mathcal{R}$ modulo the ideal of noncuppable degrees.
1961392
Degrees of Weakly Computable Reals
This paper studies the degrees of weakly computable reals. It is shown that certain types of limit-recursive reals are Turing incomparable to all weakly computable reals except the recursive and complete ones. Furthermore, it is shown that an r.e. Turing degree is array-recursive iff every real in it is weakly computable.
9960122
Dynamic Zone-Balancing of Topology-Aware Peer-to-Peer Networks
Building a topology-aware peer-to-peer overlay network can bring many advantages, such as providing locality-aware connectivity and reducing routing path length. While its benefits on performance have been recognized, an uneven overlay zone distribution has emerged. Recent work has shown that topology-aware neighbor selection during construction can aggravate the unbalance of zone distribution while it reduces routing path length. The imbalance in zone sizes may lead to performance decrease and an unfair load distribution. 
 
In this paper, we present an even topology-aware peer-to-peer network based on De Bruijn Graph by developing a dynamic zone-balancing approach.
13757062
Faster solution to the maximum quartet consistency problem with constraint programming
Evolution is an important sub-area of study in biological science, whereby the evolutionary history, or phylogeny, would shed light on the genetic linkage and the functional correlation for the species under consideration. Many kinds of species data can be deployed for the task and many phylogeny reconstruction methods have been examined in the literature. A quartet approach is to build a local phylogeny for every 4 species, which is called a quartet for these 4 species, and then to assemble a phylogeny for the whole set of species satisfying the topological constraints imposed by these quartets built. In practice, those predicted quartets might not agree each other and the optimization problem, the well-known Maximum Quartet Consistency (MQC) problem, is to construct a phylogeny to satisfy a maximum number of the predicted quartets. An equivalent representation for the MQC problem through searching for a certain ultrametric matrix via Answer Set Programming has recently been proposed. This paper follows the approach and presents a number of optimization techniques to speed up the searching process. The experimental results on both the simulated and real datasets suggest that the new representation combined with Constraint Programming presents a unique perspective to the MQC problem.
16585637
Learning with non-metric proximity matrices
Many emerging applications formulate non-metric proximity matrices (non-positive semidefinite), and hence cannot fit into the framework of kernel machines. A popular approach to this problem is to transform the spectrum of the similarity matrix so as to generate a positive semidefinite kernel matrix. In this paper, we explore four representative transformation methods: denoise, flip, diffusion, and shift. Theoretically, we discuss a generalization problem where the test data are not available during transformation, and thus propose an efficient algorithm to address the problem of updating the cross-similarity matrix between test and training data. Extensive experiments have been conducted to evaluate the performance of these methods on several real-world (dis)similarity matrices with semantic meanings.
4178545
Data placement and query processing based on RPE parallelisms
The basic idea behind parallel database systems is to perform operations in parallel to reduce the response time and improve the system throughput. Data placement is a key factor on the performance of parallel database systems. This paper proposes two data partition strategies to decluster XML documents with very large size, path schema based path instance balancing (PSPIB) strategy, in which all path instances with the same path schema in a data tree are declustered evenly over all sites, and node schema based node round-robin (NSNRR) strategy, in which all node objects with the same node schema in a data tree are declustered over all sites in a round-robin way. Accordingly, two query processing algorithms are proposed based on the two partition methods, parallel path merge (PPM) algorithm and parallel pipelining path join (PPPJ) algorithm. The performance analysis and evaluation on the two data placement strategies and corresponding query processing algorithms are given in this paper.
6594297
Generic Universal Switch Blocks
A switch block M with W terminals on each side is said to be universal if every set of nets satisfying the dimension constraint (i.e., the number of nets on each side of M is at most W) is simultaneously routable through M. In this paper, we present an algorithm to construct N-sided universal switch blocks with W terminals on each side. Each of our universal switch blocks has (/sub 2//sup N/) W switches and switch-block flexibility N-1 (i.e., F/sub S/=N-1). We prove that no switch block with less than (/sub 2//sup N/)W switches can be universal. We also compare our universal switch blocks with others of the topology associated with Xilinx XC4000-type FPGAs. To explore the area performance of the universal switch blocks, we develop a detailed router for hierarchical FPGAs (HFPGAs) with 5-sided switch blocks. Experimental results demonstrate that our universal switch blocks improve routability at the chip level. Based on extensive experiments, we also provide key insights into the interactions between switch-block architectures and routing.