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.
9638835
Isolation and Lattice Embeddings
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.
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)
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.
1594579
GPSS Simulation Study of Quality Inspection System
1975159
Formulating distance functions via the kernel trick
Tasks of data mining and information retrieval depend on a good distance function for measuring similarity between data instances. The most effective distance function must be formulated in a context-dependent (also application-, data-, and user-dependent) way. In this paper, we propose to learn a distance function by capturing the nonlinear relationships among contextual information provided by the application, data, or user. We show that through a process called the "kernel trick," such nonlinear relationships can be learned efficiently in a projected space. Theoretically, we substantiate that our method is both sound and optimal. Empirically, using several datasets and applications, we demonstrate that our method is effective and useful.
22669962
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 (Y.W. Chang et al., 1996). 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. Further, the decomposition property of a universal switch block provides a key insight into its layout implementation with a smaller silicon area. We also compare our universal switch blocks with others of the topology associated with Xilinx XC4000-type FPGAs. Experimental results demonstrate that our universal switch blocks improve routability at the chip level.
18105952
Adapting Prime Number Labeling Scheme for Directed Acyclic Graphs
Directed Acyclic Graph(DAG) could be used for modeling subsumption hierarchies. Several labeling schemes have been proposed or tailored for indexing DAG in order to efficiently explore relationships in such hierarchy. However few of them can satisfy all the requirements in response time, space, and effect of updates simultaneously. In this paper, the prime number labeling scheme is extended for DAG. The scheme invests intrinsic mapping between integer divisibility and subsumption hierarchy, which simplifies the transitive closure computations and diminishes storage redundancy, as well as inherits the dynamic labeling ability from original scheme. Performance is further improved by introducing some optimization techniques. Our extensive experimental results show that prime number labeling scheme for DAG outperforms interval-based and prefix-based labeling schemes in most cases.
1677219
Application of Smodels in Quartet Based Phylogeny Construction
Evolution is an important sub-area of study in biological science, where given a set of taxa, the goal is to reconstruct their evolutionary history, or phylogeny. One very recent approach is to predict a local phylogeny for every subset of 4 taxa, called a quartet topology, and then to assemble a phylogeny for the whole set of taxa satisfying these predicted quartet topologies. In general, the predicted quartet topologies might not always agree with each other, and thus the objective function becomes to satisfy a maximum number of them. This is the well known Maximum Quartet Consistency (MQC) problem. In the past, the MQC problem has been solved by dynamic programming and the so-called fixed-parameter method. Recently, we have proposed to solve the MQC in answer set programming. In this note, we summarize the theoretical results of this approach and report new experimental results for the purpose of comparison, which show that our approach in answer set programming is favored over the existing approaches based on dynamic programming and fixed-parameter method. In particular, some of the hard instances (where the error ratio is high) that were not reported to be solved in other approaches can now be solved in our approach.