In this paper, a quasi-synchronous code-division multiple-access (QS-CDMA) is investigated for application in the reverse link of a microcellular or indoor mobile communication environment. In a QS-CDMA system, the relative time delay between the signals of different users is normally restricted within a few chips. Generalized orthogonal (GO) codes added with guard chips are employed as the spreading sequences in this paper and the strict timing error restrictions for BPSK and M-QAM modulation schemes are derived based on the correlation properties of GO code set which determines the multiple access interference (MAI). The results reveal that the system employing GO code set with bigger GO zone can tolerate more serious timing error, and higher order modulation schemes require stricter synchronization. Based on the system model presented, the BER performance for BPSK and M-QAM is evaluated by Gaussian Approximation (GA) and Monte Carlo simulation. The system capacity in terms of acquirable total bit rates are also evaluated, revealing that if system synchronization error is limited within the GO zone, M-QAM scheme can be utilized to improve the system capacity.

In this paper, we give an algorithm for the node-to-set disjoint paths problem in pancake graphs with its evaluation results. The algorithm is of polynomial order of n for an n-pancake graph. It is based on recursion and divided into two cases according to the distribution of destination nodes in classes into which all the nodes in a pancake graph are categorized. The sum of lengths of paths obtained and the time complexity of the algorithm are estimated and the average performance is evaluated based on computer simulation.

Based on the dimensionality reduction technique and the solution for proximate points problem, we achieve the optimality of the three-dimensional Euclidean distance transform (3D_EDT) computation. For an N N N binary image, our algorithms for both 3D_EDT and its applications can be performed in O (log log N) time using CRCW processors or in O (log N) time using EREW processors. To the best of our knowledge, all results described above are the best known. As for the n-dimensional Euclidean distance transform (nD_EDT) and its applications of a binary image of size Nn, all of them can be computed in O (nlog log N) time using CRCW processors or in O (nlog N) time using EREW processors.

A Distributed Computing System (DCS) contributes in proper partitioning of the tasks into modules and allocating them to various nodes so as to enable parallel execution of their modules by individual different processing nodes of the system. The scheduling of various modules on particular processing nodes may be preceded by appropriate allocation of modules of the different tasks to various processing nodes and then only the appropriate execution characteristic can be obtained. A number of algorithms have been proposed for allocation of tasks in a DCS. Most of the solutions proposed had simplifying assumptions. The very first assumption has been: consideration of a single task with their corresponding modules only; second, no consideration of the status of processing nodes in terms of the previously allocated modules of various tasks and third, the capacity and capability of the processing nodes. This work proposes algorithms for a realistic situation wherein multiple tasks with their modules compete for execution on a DCS dynamically considering their architectural capability. In this work, we propose two algorithms based on the two well-known A* and GA for the task allocation models. The paper explains the algorithms elaborately by illustrated examples and presents a comparative performance study among our algorithms and the algorithms for task allocation proposed in the various literatures. The results demonstrate that our GA based task allocation algorithm achieves better performance compared with the other algorithms.

This paper introduces a 1-inkdot two-way alternating pushdown automaton which is a two-way alternating pushdown automaton (2apda) with the additional power of marking at most 1 tape-cell on the input (with an inkdot) once. We first investigate a relationship between the accepting powers of sublogarithmically space-bounded 2apda's with and without 1 inkdot, and show, for example, that sublogarithmically space-bounded 2apda's with 1 inkdot are more powerful than those which have no inkdots. We next investigate an alternation hierarchy for sublogarithmically space-bounded 1-inkdot 2apda's, and show that the alternation hierarchy on the first level for 1-inkdot 2apda's holds, and we also show that 1-inkdot two-way nondeterministic pushdown automata using sublogarithmic space are incomparable with 1-inkdot two-way alternating pushdown automata with only universal states using the same space.

In light of the increasing number of computer applications that rely heavily on multimedia data, the database community has focused on the management and retrieval of multidimensional data. Nearest Neighbor queries (NN queries) have been widely used to perform content-based retrieval (e.g., similarity search) in multimedia applications. Incremental NN (INN) query is a kind of NN queries and can also be used when the number of the NN objects to be retrieved is not known in advance. This paper points out the weaknesses of the existing INN search algorithms and proposes a new one, called Batch-Incremental Nearest Neighbor search algorithm (denoted B-INN search algorithm), which can be used to process the INN query efficiently. The B-INN search algorithm is different from the existing INN search algorithms in that it does not employ the priority queue that is used in the existing INN search algorithms and is very CPU and memory intensive for large databases in high-dimensional spaces. And it incrementally reports b(b > 1) objects simultaneously (Batch-Incremental), whereas the existing INN search algorithms report the neighbors one by one. In order to implement the B-INN search, a new search (called k-d-NN search) with a new pruning strategy is proposed. Performance tests indicate that the B-INN search algorithm clearly outperforms the existing INN search algorithms in high-dimensional spaces.

In this paper, we propose an answer seeking algorithm for question answering that integrates structural matching and paraphrasing, and report the results of our empirical evaluation conducted with the aim of examining effects of incorporating those two components. According to the results, the contribution of structural matching and paraphrasing was not so large as expected. Based on error analysis, we conclude that structural matching-based approaches to answer seeking require technologies for (a) coreference resolution, (b) processing of parse forests instead of parse trees, and (c) large-scale acquisition of paraphrase patterns.

Automatic text summarization has the goal of reducing the size of a document while preserving its content. Generally, producing a summary as extracts is achieved by including only sentences which are the most topic-related. DOCUSUM is our summarization system based on a new topic keyword identification method. The process of DOCUSUM is as follows. First, DOCUSUM converts the content words of a document into elements of a context vector space. It then constructs lexical clusters from the context vector space and identifies core clusters. Next, it selects topic keywords from the core clusters. Finally, it generates a summary of the document using the topic keywords. In the experiments on various compression ratios (the compression of 30%, the compression of 10%, and the extraction of the fixed number of sentences: 4 or 8 sentences), DOCUSUM showed better performance than other methods.

This paper proposes a statistical method of acquiring knowledge about the abbreviation possibility of some of multiple adnominal phrases. Our method calculates weight values of multiple adnominal phrases by mutual information based on the strength of relation between the adnominal phrases and modified nouns. Among adnominal phrases, those having relatively low weight values are deleted. The evaluation of our method by experiments shows that precision attains about 84.1% and recall attains about 59.2%, respectively.

Retrieval effectiveness depends on both the retrieval model and how terms are extracted and indexed. For Chinese, Japanese and Korea text, there are no spaces to delimit words. Indexing using hybrid terms (i.e. words and bigrams) was found to be effective and efficient using the 2-Poisson model in NTCIR-III open evaluation workshop. Here, we explore another Okapi weight, BM25, based on the 2-Poisson model and compared their performances with bigram and word indexing strategies. Results show that word indexing is the most efficient in terms of indexing time and storage but hybrid term indexing requires the least amount of retrieval time per query. Without pseudo-relevance feedback (PRF), our BM25 appeared to yield better retrieval effectiveness performance for short queries. With PRF, our implementation of the BM11 weights, which are a simplified version of BM25, with hybrid term indexing remains the most effective combination for retrieval in this study.

Document retrieval is a fundamental but important task for intelligent access to a huge amount of information stored in documents. Although the history of its research is long, it is still a hard task especially in the case that lengthy documents are retrieved with very short queries (a few keywords). For the retrieval of long documents, methods called passage-based document retrieval have proven to be effective. In this paper, we experimentally show that a passage-based method based on window passages is also effective for dealing with short queries on condition that documents are not too short. We employ a method called "density distributions" as a method based on window passages, and compare it with three conventional methods: the simple vector space model, pseudo relevance feedback and latent semantic indexing. We also compare it with a passage-based method based on discourse passages.

In most cases of distributed memory computations, node programs are executed on processors according to the owner computes rule. However, owner computes rule is not best suited for irregular application codes. In irregular application codes, use of indirection in accessing left hand side array makes it difficult to partition the loop iterations, and because of use of indirection in accessing right hand side elements, we may reduce total communication by using heuristics other than owner computes rule. In this paper, we propose a communication cost reduction computes rule for irregular loop partitioning, called least communication computes rule. We partition a loop iteration to a processor on which the minimal communication cost is ensured when executing that iteration. Then, after all iterations are partitioned into various processors, we give global vs. local data transformation rule, indirection arrays remapping and communication optimization methods. The experimental results show that, in most cases, our approaches achieved better performance than other loop partitioning rules.

Optical Character Reader (OCR) incorrect recognition is a serious problem when searching for OCR-scanned documents in databases such as digital libraries. In order to reduce costs, this paper proposes fuzzy retrieval methods for English text containing errors in the recognized text without correcting the errors manually. The proposed methods generate multiple search terms for each input query term based on probabilistic automata which reflect both error-occurrence probabilities and character-connection probabilities. Experimental results of test-set retrieval indicate that one of the proposed methods improves the recall rate from 95.96% to 98.15% at the cost of a decrease in precision from 100.00% to 96.01% with 20 expanded search terms.

In many cryptographic applications, a large-order finite field is used as a definition field, and accordingly, many researches on a fast implementation of such a large-order extension field are reported. This paper proposes a definition field Fpm with its characteristic p a pseudo Mersenne number, the modular polynomial f(x) an irreducible all-one polynomial (AOP), and using a suitable basis. In this paper, we refer to this extension field as an all-one polynomial field (AOPF) and to its basis as pseudo polynomial basis (PPB). Among basic arithmetic operations in AOPF, a multiplication between non-zero elements and an inversion of a non-zero element are especially time-consuming. As a fast realization of the former, we propose cyclic vector multiplication algorithm (CVMA), which can be used for possible extension degree m and exploit a symmetric structure of multiplicands in order to reduce the number of operations. Accordingly, CVMA attains a 50% reduction of the number of scalar multiplications as compared to the usually adopted vector multiplication procedure. For fast realization of inversion, we use the Itoh-Tsujii algorithm (ITA) accompanied with Frobenius mapping (FM). Since this paper adopts the PPB, FM can be performed without any calculations. In addition to this feature, ITA over AOPF can be composed with self reciprocal vectors, and by using CVMA this fact can also save computation cost for inversion.

Analog Hopfield neural networks (HNNs) have so far been used to solve many kinds of optimization problems, in particular, combinatorial problems such as the TSP, which can be described by an objective function and some equality constraints. When we solve a minimization problem with equality constraints by using HNNs, however, the constraints are satisfied only approximately. In this paper we propose a circuit which rigorously realizes the equality constraints and whose energy function corresponds to the prescribed objective function. We use the SPICE program to solve circuit equations corresponding to the above circuits. The proposed method is applied to several kinds of optimization problems and the results are very satisfactory.

Frequency-domain representation of the well-known time-domain rake combining for the antenna diversity reception of DS-CDMA signals is derived. Two receiver structures using frequency-domain rake combining are presented. Frequency-domain rake combining can alleviate the complexity problem of the time-domain rake arising from too many paths in a severe frequency selective fading channel at the cost of guard interval insertion. The results shown in this paper show a possibility that a DS-CDMA approach still remain to be promising for broadband wireless access technique.

We present the channel capacity, specifically the mutual information, of an additive white Gaussian noise (AWGN) channel in the presence of phase noise, and investigate the effect of phase noise impairment on powerful error-correcting codes (ECCs) that normally operate in low signal-to-noise ratio (SNR) regions. This channel-induced impairment is common in digital coherent transmission systems and is caused by imperfect carrier tracking of the phase error detector for coherent demodulation. It is shown through semi-analytical derivation that decreasing the information rate from its ideal capacity to an information rate lower than its inherent capacity significantly mitigates the impairment caused by phase noise, and that operating systems in the low SNR region also lessen the phase noise impairment by transforming typical phase noise behavior into Gaussian-like behavior. We also demonstrate by computer simulation using turbo-trellis coded modulation (TTCM) with high-order quadrature amplitude modulation (QAM) signals that the use of capacity-approaching codes (CACs) makes transmission systems invulnerable to phase noise. To verify the effect of CACs on phase noise, simulation results of TTCM are also compared to that of trellis-coded modulation (TCM), which is used as an example of a conventional ECC operating at a relatively high SNR.

A low complexity multi-user receiver with blind channel estimation and multiple access interference (MAI) suppression is proposed for a CDMA system under multipath fading and frequency offset. The design of the receiver involves the following procedure. First, a method of joint MAI suppression and channel estimation is developed based on the generalized sidelobe canceller (GSC) technique. In particular, channel estimates are obtained blindly in the form of the effective composite signature vectors (CSV) of the users. Second, a low-complexity partially adaptive (PA) realization of the receiver is proposed which incorporates reduced-rank processing based on the information of multi-user CSV's. By a judiciously designed decorrelating procedure, a new PA receiver is obtained with a much lower complexity. Finally, pilot symbols assisted frequency offset estimation and channel gain compensation give the estimate of users' symbols. Further performance enhancement is achieved by a decision aided scheme in which the signal is reconstructed and subtracted from the receiver input data, leading to significantly faster convergence. The proposed receiver is shown to be robust to multipath fading and frequency offset, and achieves nearly the same performance of the optimal maximum SINR and MMSE receivers with a much lower overhead for pilot symbols.

Applying gang scheduling can alleviate the blockade problem caused by exclusively used space-sharing strategies for parallel processing. However, the original form of gang scheduling is not practical as there are several fundamental problems associated with it. Recently many researchers have developed new strategies to alleviate some of these problems. Unfortunately, one important problem has not been so far seriously addressed, that is, how to set the length of time slots to obtain a good performance of gang scheduling. In this paper we present a strategy to deal with this important issue for efficient gang scheduling.

Let us introduce n ( 2) nonlinear mappings fi (i = 1,2,,n) defined on complete linear metric spaces (Xi-1,ρ) (i = 1,2,,n), respectively, and let fi: Xi-1 Xi be completely continuous on bounded convex closed subsets Xi-1,(i = 1,2,,n 0), such that fi() . Moreover, let us introduce n fuzzy-set-valued nonlinear mappings Fi: Xi-1 Xi {a family of all non-empty closed compact fuzzy subsets of Xi}. Here, we have a fixed point theorem on the recurrent system of β-level fuzzy-set-valued mapping equations: xi Fiβ(xi-1,fi(xi-1)), (i = 1,2,,n 0), where the fuzzy set Fi is characterized by a membership function µFi(xi): Xi [0,1], and the β-level set Fiβ of the fuzzy set Fi is defined as Fiβ {ξi Xi | µFi(ξi) β}, for any constant β (0,1]. This theorem can be applied immediately to discussion for characteristics of ring nonlinear network systems disturbed by undesirable uncertain fluctuations and to fine estimation of available behaviors of those disturbed systems. In this paper, its mathematical situation and proof are discussed, in detail.