We briefly survey a number of important recent achievements in Theoretical Computer Science (TCS), especially Computational Complexity Theory. We will discuss the PCP Theorem, its implications to inapproximability on combinatorial optimization problems; space bounded computations, especially deterministic logspace algorithm for undirected graph connectivity problem; deterministic polynomial-time primality test; lattice complexity, worst-case to average-case reductions; pseudorandomness and extractor constructions; and Valiant's new theory of holographic algorithms and reductions.

A typed category theory is proposed for the abstract description of knowledge and knowledge processing. It differs from the traditional category theory in two directions: all morphisms have types and the composition of morphisms is not necessary a morphism. Two aspects of application of typed category theory are discussed: cones and limits of knowledge complexity classes and knowledge completion with pseudo-functors.

A homomorphism \varphi of logic programs from P to P' is a function mapping Atoms (P) to Atoms (P') and it preserves complements and program clause. For each definite program clause a\leftarrow a_1, \ldots, a_n\in P it implies that \varphi(a)\leftarrow \varphi(a_1), \ldots, \varphi(a_n) is a program clauses of P' . A homomorphism \varphi is an isomorphism if \varphi is a bijection. In this paper, the complexity of the decision problems on homomorphism and isomorphism for definite logic programs is studied. It is shown that the homomorphism problem ( HOM - LP ) for definite logic programs is NP --complete, and the isomorphism problem ( ISO - LP ) is equivalent to the graph isomorphism problem ( GI \,).

In this paper, a new method, named as L-tree match, is presented for extracting data from complex data sources. Firstly, based on data extraction logic presented in this work, a new data extraction model is constructed in which model components are structurally correlated via a generalized template. Secondly, a database-populating mechanism is built, along with some object-manipulating operations needed for flexible database design, to support data extraction from huge text stream. Thirdly, top-down and bottom-up strategies are combined to design a new extraction algorithm that can extract data from data sources with optional, unordered, nested, and/or noisy components. Lastly, this method is applied to extract accurate data from biological documents amounting to 100GB for the first online integrated biological data warehouse of China.

An important concept proposed in the early stage of robot path planning field is the shrinking of a robot to a point and meanwhile the expanding of obstacles in the workspace as a set of new obstacles. The resulting grown obstacles are called the Configuration Space (Cspace) obstacles. The find-path problem is then transformed into that of finding a collision-free path for a point robot among the Cspace obstacles. However, the research experiences have shown that the Cspace transformation is very hard when the following situations occur: 1) both the robot and obstacles are not polygons, and 2) the robot is allowed to rotate. This situation gets even worse when the robot and obstacles are three dimensional (3D) objects with various shapes. For this reason, direct path planning approaches without the Cspace transformation is quite useful and expected. Motivated by the practical requirements of robot path planning, a generalized constrained optimization problem (GCOP) with not only logic AND but also logic OR relationships was proposed and a mathematical solution developed previously. This paper inherits the fundamental ideas of inequality and optimization techniques from the previous work, converts the obstacle avoidance problem into a semi-infinite constrained optimization problem with the help of the mathematical transformation, and proposes a direct path planning approach without Cspace calculation, which is quite different from traditional methods. To show its merits, simulation results in 3D space have been presented.

Currently, schema integration frameworks use approaches like rule-based, machine learning, etc. This paper presents an ontology-based wrapper-mediator framework that uses both the rule-based and machine learning strategies at the same time. The proposed framework uses global and local ontologies for resolving syntactic and semantic heterogeneity, and XML for interoperability. The concepts in the candidate schemas are merged on the basis of the similarity coefficient, which is calculated using the defined rules and the prior mappings stored in the case-base.

Mobile ad hoc networks (MANETs) are gaining a lot of attention in research lately due to their importance in enabling mobile wireless nodes to communicate without any existing wired or predetermined infrastructures. Furthermore, in order to support the growing need for multimedia and realtime applications, quality of service (QoS) support by the networking protocol is required. Several important QoS parameters that are needed by such applications can be identified. They include bandwidth, end-to-end delay, delay jitter, and bit error rate. A good amount of research has been developed in this area covering different issues and challenges such as developing routing protocols that support bandwidth reservation and delay management. In this paper, the current state of research for QoS support in TDMA-based MANETs at different layers of the networking model is presented and categorized. In addition, the current issues and future challenges involved in this exciting area of research are also included.

Indexing techniques have been developed for wireless data broadcast environments, in order to conserve the scarce power resources of the mobile clients. However, the use of interleaved index segments in a broadcast cycle increases the average access latency for the clients. In this paper, the broadcast-based spatial query processing methods (BBS) are presented for the location-based services. In the BBS, broadcasted data objects are sorted sequentially based on their locations, and the server broadcasts the location dependent data along with an index segment. Then, a sequential prefetching and caching scheme is designed to reduce the query response time. The performance of this scheme is investigated in relation to various environmental variables, such as the distributions of the data objects, the average speed of the clients and the size of the service area.

In wormhole meshes, a reliable routing is supposed to be deadlock-free and fault-tolerant. Many routing algorithms are able to tolerate a large number of faults enclosed by rectangular blocks or special convex, none of them, however, is capable of handling two convex fault regions with distance two by using only two virtual networks. In this paper, a fault-tolerant wormhole routing algorithm is presented to tolerate the disjointed convex faulty regions with distance two or no less, which do not contain any nonfaulty nodes and do not prohibit any routing as long as nodes outside faulty regions are connected in the mesh network. The processors' overlapping along the boundaries of different fault regions is allowed. The proposed algorithm, which routes the messages by X - Y routing algorithm in fault-free region, can tolerate convex fault-connected regions with only two virtual channels per physical channel, and is deadlock- and livelock-free. The proposed algorithm can be easily extended to adaptive routing.

In this paper, a quantitative QoS management implement mechanism in IP-DiffServ is presented. The approach has three merits: (1) it optimizes both the route selected for service class by traffic engineering in network layer and the service class selected for the user services by network plan in service layer, (2) it ensures quantitative QoS for the user service in DiffServ, (3) it achieves high resource utilization, and achieves better performance with less cost for the user service and selected route. Simulation has verified these merits.

In this paper, it is proved that, given 3 control points A , B and C , if the camera's optical center O lies on one of the three planes perpendicular to the plane ABC and going through one of the three altitudes of the triangle ABC , and additionally its projection on the plane ABC is within the circumscribed circle of the triangle, that is, O is within the so-called ``danger cylinder'', then the corresponding P3P problem \ O, ( ABC )\ must have 4 positive solutions. This result is purely geometrical, and more instructive. It can bring some new insight into a better understanding of multiple-solution problem in the P n P problem, and could be used as some theoretical guide to arrange control points in real applications.

In this paper, a new technique is proposed for rotation, scaling and translation (RST) invariant image watermarking based on log-polar mappings (LPM) and phase-only filtering (POF). The watermark is embedded in the LPM of Fourier magnitude spectrum of the original image, and a small portion of resulting LPM spectrum is used to calculate the watermark positions. This technique avoids computing inverse log-polar mapping (ILPM) to preserve the quality of the watermarked image, and avoids exhaustive search to save computation time and reduce false detection. Experimental results demonstrate that the digital watermarking technique is invariant and robust to rotation, scaling, and translation transformation.

This paper proposes a new algorithm, called Edge-based Texture Driven Shape Model (E-TDSM), for non-frontal face alignment task. First, the texture is defined as the un-warped edge image contained in the shape rectangle; then, a Bayesian network is constructed to describe the relationship between the shape and texture models; finally, Expectation-Maximization (EM) approach is utilized to infer the optimal texture and position parameters from the observed shape and texture information. Compared with the traditional shape localization algorithms, E-TDSM has the following advantages: 1) the un-warped edge-based texture can better predict the shape and is more robust to the illumination and expression variation than the conventional warped gray-level based texture; 2) the presented Bayesian network indicates the logic structure of the face alignment task; and 3) the mutually enhanced shape and texture observations are integrated to infer the optimal parameters of the proposed Bayesian network using EM approach. The extensive experiments on non-frontal face alignment task demonstrate the effectiveness and robustness of the proposed E-TDSM algorithm.

Current investigations on visual information retrieval are generally content-based methods. The significant difference between similarity in low-level features and similarity in high-level semantic meanings is still a major challenge in the area of image retrieval. In this work, a scheme for constructing visual ontology to retrieve art images is proposed. The proposed ontology describes images in various aspects, including type & style, objects and global perceptual effects. Concepts in the ontology could be automatically derived. Various art image classification methods are employed based on low-level image features. Non-objective semantics are introduced, and how to express these semantics is given. The proposed ontology scheme could make users more naturally find visual information and thus narrows the ``semantic gap''. Experimental implementation demonstrates its good potential for retrieving art images in a human-centered manner.

Algorithms to generate a triangular or a quadrilateral interpolant with G^1 -continuity are given in this paper for arbitrary scattered data with associated normal vectors over a prescribed triangular or quadrilateral decomposition. The interpolants are constructed with a general method to generate surfaces from moving B\'ezier curves under geometric constraints. With the algorithm, we may obtain interpolants in complete symbolic parametric forms, leading to a fast computation of the interpolant. A dynamic interpolation solid modelling software package DISM is implemented based on the algorithm which can be used to generate and manipulate solid objects in an interactive way.

Coverage evaluation is indispensable for verification via simulation. As the functional complexity of modern design is increasing at a breathtaking pace, it is requisite to take observability into account. Unfortunately, nowadays coverage metrics taking observability into account are not very satisfactory. On the one hand, for the observability assessment algorithms proposed up to now, the overhead of computing is large, so they could not be integrated into simulation tools easily. On the other hand, the vector generation methods involving the metrics taking observability into account are not very efficient, and there exists a disconnection between these metrics and the vector generation process. In this paper, some original ideas for the problems above are presented. (1) Precise and concise abstract representations from HDL (Hardware Description Language) descriptions at RTL (Register Transfer Level) are presented to model observability information. (2) A novel observability evaluation method based on the proposed models is introduced. This method is more computationally efficient than prior efforts to assess observability and it could be integrated into compilers and simulators easily. (3) A new simulation vector generation procedure involving the observability-enhanced statement coverage metric is developed. The method is simulation-based and driven by the distribution of unobserved statements. During this procedure, the proposed algorithm always tries to cover all unobserved statements, and reduce unnecessary backtracking, so it is efficient. The methods proposed have been implemented as a prototype tool for VHDL designs, and the results on benchmarks show significant benefits.

Modern VLSI circuits provide adequate on-chip resources. So that online testing and retry integrated into a chip are absolutely necessary for system-on-a-chip technology. This paper firstly proposes a general online testing plus retrying structure. Obviously, although retry can mask transient or intermittent faults, it is useless for handling permanent faults generally. To solve this problem, this paper presents a novel dual modular redundancy (DMR) structure using complementary logic---alternating-complementary logic (CL-ACL) switching mode. During error-free operation, the CL-ACL structure operates by complementary logic mode. After an error is detected, it retries by alternating logic mode. If all errors belong to single or multiple temporary 0/1-error or stuck-at-error produced by one module, then these errors can be corrected effectively. The results obtained from the simulation validate the correctness of the CL-ACL structure. Analytic results show that the delay of the CL-ACL structure is dramatically less than that of a DMR structure using alternating-complementary logic mode.

Reed-Muller logic is becoming increasingly attractive. However, its synthesis and optimization are difficult especially for mixed polarity Reed-Muller logic. In this paper, a function is expressed into a truth vector. Product shrinkage, general sum shrinkage (GSS), elimination and extraction operators are proposed to shrink the truth vector. A novel algorithm is presented to derive a compact Multi-level Mixed Polarity Reed-Muller Form (MMPRMF) starting from a given fixed polarity truth vector. The results show that a significant area improvement can be made compared with published results.

As the technology advances into deep sub-micron era, crosstalk reduction is of paramount importance for signal integrity. Simultaneous shield insertion and net ordering (SINO) has been shown to be effective to reduce both capacitive and inductive couplings. As it introduces extra shields, area minimization is also critical for an efficient SINO algorithm. In this paper, three novel algorithms using fewer shields to solve crosstalk reduction problem with RLC noise constraint are proposed, namely, net coloring (NC), efficient middle shield insertion (EMSI) and NC+EMSI two-step algorithm. Compared with the corresponding algorithms in previous work, these algorithms can reduce shielding area up to 25.77% , 46.19%, and 7.17% , respectively, with short runtime.