Semi-input-memory finite automata, a kind of finite automata introduced by the first author of this paper for studying error propagation, are a generalization of input-memory finite automata by appending an autonomous finite automaton component. In this paper, we give a characterization of the structure of weakly invertible semi-input-memory finite automata with delay 1, in which the state graph of each autonomous finite automaton is a cycle. From a result on mutual invertibility of finite automata obtained by the authors recently, it leads to a characterization of the structure of feedforward inverse finite automata with delay 1.

Chinese-English machine translation is a significant and challenging problem in information processing. The paper presents an interlingua-based Chinese-English natural language translation system (ICENT). It introduces the realization mechanism of Chinese language analysis, which contains syntactic parsing and semantic analyzing and gives the design of interlingua in details. Experimental results and system evaluation are given. The result is satisfying.

Multiresolution analysis (MRA) and wavelets provide useful and efficient tools for representing functions at multiple levels of details. Wavelet representations have been used in a broad range of applications, including image compression, physical simulation and numerical analysis. In this paper, the authors construct a new class of wavelets, called four-point wavelets, based on an interpolatory four-point subdivision scheme. They are of local support, symmetric and stable. The analysis and synthesis algorithms have linear time complexity. Depending on different weight parameters w, the scaling functions and wavelets generated by the four-point subdivision scheme are of different degrees of smoothness. Therefore the user can select better wavelets relevant to the practice among the classes of wavelets. The authors apply the four-point wavelets in signal compression. The results show that the four-point wavelets behave much better than B-spline wavelets in many situations.

This paper is devoted to a new algebraic modelling approach to distributed problem-solving in multi-agent systems (MAS), which is featured by a unified framework for describing and treating social behaviors, social dynamics and social intelligence. A conceptual architecture of algebraic modelling is presented. The algebraic modelling of typical social behaviors, social situation and social dynamics is discussed in the context of distributed problem-solving in MAS. The comparison and simulation on distributed task allocations and resource assignments in MAS show more advantages of the algebraic approach than other conventional methods.

In this paper the problem of blending parametric surfaces using subdivision patches is discussed. A new approach, named removing-boundary, is presented to generate piecewise-smooth subdivision surfaces through discarding the outmost quadrilaterals of the open meshes derived by each subdivision step. Then the approach is employed both to blend parametric bicubic B-spline surfaces and to fill n-sided holes. It is easy to produce piecewise-smooth subdivision surfaces with both convex and concave corners on the boundary, and limit surfaces are guaranteed to be C^2 continuous on the boundaries except for a few singular points by the removing-boundary approach. Thus the blending method is very efficient and the blending surface generated is of good effect.

An r.e. degree c is contiguous if degwtt(A)=degwtt(B) for any r.e. sets A, B ** c. In this paper, we generalize the notation of contiguity to the structure R/M, the upper semilattice of the r.e. degree set R modulo the cappable r.e. degree set M. An element [c] ** R/M is contiguous if [degwtt(A)]=[degwtt(B)] for any r.e. sets A, B such that degT(A), degT(B)**[c]. It is proved in this paper that every nonzero element in R/M is not contiguous, I.e., for every element [c]**R/M, if [c] !=[o] then there exist at least two r.e. sets A, B such that degT(A), degT(B)**[c] and [degwtt(A)]!=[degwtt(B)].

A smoke simulation approach based on the integration of traditional particle systems and density functions is presented in this paper. By attaching a density function to each particle as its attribute, the diffusion of smoke can be described by the variation of particles' density functions, along with the effect on airflow by controlling particles' movement and fragmentation. In addition, a continuous density field for realistic rendering can be generated quickly through the look-up tables of particle's density functions. Compared with traditional particle systems, this approach can describe smoke diffusion, and provide a continuous density field for realistic rendering with much less computation. A quick rendering scheme is also presented in this paper as a useful preview tool for tuning appropriate parameters in the smoke model.

It is very important to use database technology for a large-scale system such as ERP and MIS. A good database design may improve the performance of the system. Some researches show that a g-acyclic database scheme has many good properties, e.g., each connected join expression is monotonous, which helps to improve query performance of the database system. Thus what conditions are needed to generate a g-acyclic database scheme for a given relational scheme? In this paper, the sufficient and necessary condition of the existence of g-acyclic, join-lossless and dependencies-preserved database schemes meeting 4NF is given.

With the development of the Internet, the World Wide Web has become an invaluable information source for most organizations. However, most documents available from the Web are in HTML form which is originally designed for document formatting with little consideration of its contents. Effectively extracting data from such documents remains a non-trivial task. In this paper, we present a schema-guided approach to extracting data from HTML pages. Under the approach, the user defines a schema specifying what to be extracted and provides sample mappings between the schema and the HTML page. The system will induce the mapping rules and generate a wrapper that takes the HTML page as input and produces the required data in the form of XML conforming to the user-defined schema. A prototype system implementing the approach has been developed. The preliminary experiments indicate that the proposed semi-automatic approach is not only easy to use but also able to produce a wrapper that extracts required data from inputted pages with high accuracy.

In mobile database systems, mobility of users has a significant impact on data replication. As a result, the various replica control protocols that exist today in traditional distributed and multidatabase environments are no longer suitable. To solve this problem, a new mobile database replication scheme, the Transaction-Level Result-Set Propagation (TLRSP) model, is put forward in this paper. The conflict detection and resolution strategy based on TLRSP is discussed in detail, and the implementation algorithm is proposed. In order to compare the performance of the TLRSP model with that of other mobile replication schemes, we have developed a detailed simulation model. Experimental results show that the TLRSP model provides an efficient support for replicated mobile database systems by reducing reprocessing overhead and maintaining database consistency.

Multicast offers an efficient means of distributing video contents/programs to multiple clients by batching their requests and then having them share a server's video stream. Batching customers' requests is either client-initiated or server-initiated. Most advanced client-initiated video multicasts are implemented by patching. Periodic broadcast, a typical server-initiated approach, can be entirety-based or segment-based. This paper focuses on the performance of the VoD service for popular videos. First, we analyze the limitation of conventional patching when the customer request rate is high. Then, by combining the advantages of each of the two broadcast schemes, we propose a hybrid broadcast scheme for popular videos, which not only lowers the service latency but also improves clients' interactivity by using an active buffering technique. This is shown to be a good compromise for both lowering service latency and improving the VCR-like interactivity.

In many models of all-optical routing, a set of communication paths in a network is given, and a wavelength is to be assigned to each path so that paths sharing an edge receive different wavelengths. The goal is to assign as few wavelengths as possible, in order to use the optical bandwidth efficiently. If a node of a network contains a wavelength converter, any path that passes through this node may change its wavelength. Having converters at some of the nodes can reduce the number of wavelengths required for routing. This paper presents a wavelength converter with degree 4 and gives a routing algorithm which shows that any routing with load L can be realized with L wavelengths when a node of an all-optical ring hosts such a wavelength converter. It is also proved that 4 is the minimum degree of the converter to reach the full utilization of the available wavelengths if only one node of an all-optical ring hosts a converter.

As a scalable QoS (Quality of Service) architecture, DiffServ (Differentiated Service) mainly consists of two components: traffic conditioning at the edge of the DiffServ domain and simple packet forwarding inside the DiffServ domain. DiffServ has many advantages such as flexibility, scalability and simplicity. But when providing AF (Assured Forwarding) services, DiffServ has some problems such as unfairness among aggregated flows or among micro-flows belonging to an aggregated flow. In this paper, a feedback mechanism for AF aggregated flows is proposed to solve this problem. Simulation results show that this mechanism does improve the performance of DiffServ. First, it can improve the fairness among aggregated flows and make DiffServ more friendly toward TCP (Transmission Control Protocol) flows. Second, it can decrease the buffer requirements at the congested router and thus obtain lower delay and packet loss rate. Third, it also keeps almost the same link utility as in normal DiffServ. Finally, it is simple and easy to be implemented.

Software configuration management (SCM) is an important key technology in software development. Component-based software development (CBSD) is an emerging paradigm in software development. However, to apply CBSD effectively in real world practice, supporting SCM in CBSD needs to be further investigated. In this paper, the objects that need to be managed in CBSD is analyzed and a component-based SCM model is presented. In this model, components, as the integral logical constituents in a system, are managed as the basic configuration items in SCM, and the relationships between/among components are defined and maintained. Based on this model, a configuration management system is implemented.

Parallelizing compilers have made great progress in recent years. However, there still remains a gap between the current ability of parallelizing compilers and their final goals. In order to achieve the maximum parallelism, run-time techniques were used in parallelizing compilers during last few years. First, this paper presents a basic run-time privatization method. The definition of run-time dead code is given and its side effect is discussed. To eliminate the imprecision caused by the run-time dead code, backward data-flow information must be used. Proteus Test, which can use backward information in run-time, is then presented to exploit more dynamic parallelism. Also, a variation of Proteus Test, the Advanced Proteus Test, is offered to achieve partial parallelism. Proteus Test was implemented on the parallelizing compiler AFT. In the end of this paper the program fpppp.f of Spec95fp Benchmark is taken as an example, to show the effectiveness of Proteus Test.

This paper proposes an automatic attack construction algorithm in order to find potential attacks on security protocols. It is based on a dynamic strand space model, which enhances the original strand space model by introducing active nodes on strands so as to characterize the dynamic procedure of protocol execution. With exact causal dependency relations between messages considered in the model, this algorithm can avoid state space explosion caused by asynchronous composition. In order to get a finite state space, a new method called strand-added on demand is exploited, which extends a bundle in an incremental manner without requiring explicit configuration of protocol execution parameters. A finer granularity model of term structure is also introduced, in which subterms are divided into check subterms and data subterms. Moreover, data subterms can be further classified based on the compatible data subterm relation to obtain automatically the finite set of valid acceptable terms for an honest principal. In this algorithm, terms core is designed to represent the intruder's knowledge compactly, and forward search technology is used to simulate attack patterns easily. Using this algorithm, a new attack on the Dolve-Yao protocol can be found, which is even more harmful because the secret is revealed before the session terminates.

In this paper, an approach of keyword confidence estimation is developed that well combines acoustic layer scores and syllable-based statistical language model (LM) scores. An a posteriori(AP) confidence measure and its forward-backward calculating algorithm are deduced. A zero false alarm (ZFA) assumption is proposed for evaluating relative confidence measures by word spotting task. In a word spotting experiment with a vocabulary of 240 keywords, the keyword accuracy under the AP measure is above 94%, which well approaches its theoretical upper limit. In addition, a syllable lattice Hidden Markov Model (SLHMM) is formulated and a unified view of confidence estimation, word spotting, optimal path search, and N-best syllable re-scoring is presented. The proposed AP measure can be easily applied to various speech recognition systems as well.