Abstract:In this paper, the algebraic semantics of Verilog is explored, which is a collection of laws associated with Verilog constructs. These laws provide a precise framework for describing and defining the semantics of Verilog. The special features of the semantics of Verilog are shown. All the laws presented above are sound with respect to the operational semantics, i.e., if the two processes are the two sides of a law, then they are bisimilar. At last, the completeness of the algebraic laws with respect to a subset of Verilog and the operational semantics, i.e., are explored, if such programs are bisimilar, then they are algebraically equivalent. For the proof of completeness, this method will be the discovery of a normal form program for any such programs. Each such program will have an equivalent normal form program (through transformation by the algebraic laws), but two normal form programs will be bisimilar in the operational semantics if and only if they are syntactically equivalent in a simple way. These results are of theoretical significance, for the theories of process algebra are concentrated on the channel- communication concurrent languages. But there is little work on the shared-variable concurrent languages, and a general and effective treatment to the research of such kind of complex concurrent languages is proposed in this paper.

Abstract:A computational mechanism for context-free language parsing is proposed in this paper, which is called role inverse algorithm. The mechanism is based on the assignment of appropriate roles to categories according to their contexts. A kind of effectual 搇ook ahead?function is introduced into chart parsing by this mechanism at acceptable cost. As a result, lots of useless arcs in a chart can be avoided, so that a parsing process is accelerated. This mechanism can be used in many applications, such as natural language processing.

Abstract:In this paper, an important idea of devising a quantum algorithm is introduced, based on the description and analysis of two classes of quantum search algorithms, i.e. the unstructured search algorithms and structured search algorithms. Some qualities of Grover’s search algorithm, which is the representation of the unstructured search algorithms are introduced and summarized, by analyzing its peculiar complexity, completeness, sensitivity to the errors in the mappings, and its advantages and disadvantages. On introducing structure-based search algorithm, the Tad Hogg’s series of search algorithms are referred to. They can be summarized into one universal algorithm framework, which can be separated into two parts, i.e., the problem-independent mapping and phase rotation matrix. This paper places emphasis on analyzing one of the phase adaptation strategies, and interprets how it works and what can make it more efficient. Some other factors affect the algorithm are also discussed more generally. Finally, based on the comparison and analysis of classical search algorithm and the quantum one, the thoughts behind various quantum search algorithms are illustrated.

Abstract:For medium predicate logic system MF, a new infinite value semantic interpretation that is λ-interpretation is introduced, the λ-resolution method is led into the MF. The λ-resolution principle of MF is discussed and its completeness is proved.

Abstract:A methodology is presented to construct virtual domain ontologies reusing other domain knowledge already available. This methodology uses the semantic relevance of existing domain models and domain ontologies, and proposes the possibility of building ontologies following the view of semantic match. Firstly, a structural definition of domain ontology is given. Secondly, the semantic relevance between domain model and ontologies is discussed and a definition of relevance degree is given. Based on the evolution of population, the domain ontologies constructing technologies in the terminology from genetics such as selection, clone, mutation, crossover, synthesis and transgenic are discussed. Finally, a VDO (virtual domain ontologies) constructing system is introduced, and a case study in the field of some hotels and travel agencies is demonstrated.

Abstract:The element acted as object in XYZ/E object-oriented program is agent, a module consists of a data package and a process. In this paper, the semantics of XYZ/E object-oriented programs are defined, including their language elements, under the framework of temporal logic. And several theories for proving the semantics consistency between these elements are also provided.

Abstract:Computation partition is one of the most important problems in parallel compilation and optimization. For dealing with parallel loops with determinated data distribution, a computation partition algorithm based on the subset of uniform schemes is proposed. The method of getting the subset of uniform schemes is given, as well as the algorithm of selecting the most optimized scheme under the consideration of communication and load balance. The experimental results prove that this algorithm is simpler and more effective than several previous algorithms in dealing with parallel loops, and the p_HPF compiler adopted by this algorithm can obtain good speedups and efficiencies. The compiler has been applied in the field of petroleum.

Abstract:A transactional workflow is composed of traditional flat transactions, and its execution has relaxed transactional atomicity. Due to different termination characteristics of transactions, only one workflow is allowed to execute non-compensatable transactions with current scheduling protocols. In this paper, two granularities of conflict based on transaction classes and transaction instances are defined, and a scheduling protocol by using both granularities of conflict detection is proposed. Besides generating serializable and recoverable schedules, this method provides a higher degree of concurrency in following two ways. On the one hand, the fine-grained locking mechanism based on transaction instances is used to reduce conflict possibility among concurrent workflows. On the other hand, the coarse-grained conflict mechanism based on transaction classes is used to predict future conflict among workflows, multiple workflows are therefore allowed to execute non-compensatable transactions if they will not conflict in predicated future execution.

Abstract:A scheduling algorithm based on priority table design is presented in this paper. Any two characteristic parameters (e.g., relative deadline and slack) of a task are combined to design its priority table so that the deadline is nearer or the slack is shorter, the priority is higher. The priority of a task is uniquely determined by its relative deadline and slack. For any task, its unique priority can be obtained by using Lagrange interposing algorithm on the designed priority table. Compared with the classical EDF and LSF policies, simulated results show that the proposed algorithm improves the efficiency of task scheduling, i.e., to designate the priority of a task, increases the succeed ratio of task scheduling, and decreases the missed deadline percentage. The proposed algorithm can be applied to dynamically schedule real-time tasks in real-time systems.

Abstract:An agent-oriented programming language with intention driver is proposed, which is called AOPLID. Based on open situation calculus, AOPLID can be regarded as an improvement of GOLOG that is based on situation calculus. AOPLID can formalize some elements of the agent’s mental state, namely belief, intention, capability and strategy. A belief revision operator is introduced in AOPLID to deal with the communication and exogenous events. AOPLID solves the problems GOLOG faces, such as inconvenience of describing the agent’s mental state, lack of communication. The syntax of the AOPLID and its semantic under the OSC are presented. An example program of AOPLID that describes the coffee machine is given too.

Abstract:Pen-Based user interfaces provide more natural interactions for users. However, it is difficult to be constructed because a usable pen-based user interface generally involves multiple areas and interdisciplinary knowledge. In this paper, the design and implementation of a toolkit, named Penbuilder, is described systematically, supporting the development of pen-based user interfaces. It is designed based on the attributes of pen interaction and ubiquitous computing. It offers high-level supports to developers. Based on Penbuilder, several typical prototypes of pen interaction have been constructed, which demonstrates the capability of Penbuilder for easy construction and fast-prototyping of pen-based user interfaces.

Abstract:As the component repositories scaling up and the reuse practice deepening, representing and retrieving software components gains more attention from software engineering researchers. A matching model is proposed in this paper to retrieve reusable components classified in faceted scheme includes three levels and five schemes. A generic matching algorithm is provided and analysis and test are done on its specialized implement and relevant time complexity. The results show that this solution is feasible and effective for the component retrieval.

Abstract:DHDF (dynamic homogeneous dataflow) is the kernel of most graphic programming platform. For the natural data-driven property, the dynamic homogeneous dataflow can not work properly with the event-driven operating system, which leads to two demerits: one is inefficiency in CPU using, the other is low respond speed and poor in real time performance. An ECDF (event triggered concurrent dataflow) model and its formal description are presented in this paper. Based on multi-thread and event-triggered mechanism, the real time performance and execution efficiency of dataflow-based system are improved. The experimental results of a test system prove that the event-driven concurrent dataflow can ameliorate the performance of dataflow-based system to a certain degree in most conditions comparing with the dynamic homogeneous dataflow model. ECDF model is also suited for the Reactive systems design, and high-speed burst-data flow processing especially.

Abstract:A technology of binding time analysis for implementing partial evaluation of object-oriented programming languages is proposed in this paper. By tracing context-sensitivity of reference variables and pointer variables, the new approach can deal with elements of partly static data structure, such as attributes of each object and elements of each array. The new approach uses a two-level BTA environment to hold BTA states for static variables and local variables. The objects created at different program points are represented by a kind of specific handle. The BTA state of a reference variable is represented by a set of such handles. The algorithm of a forward analysis and backward analysis are presented. They are used to annotate source program, with BTA environment to trace binding time of various kind of variables including identifier of array, object and reference. The binding time analysis has been implemented for Java. It is able to analyse most single thread Java programs and support partial evaluation for Java with higher performance.

Abstract:Based on macro-time and micro-time, a BDI-Agent model with branch time tree is defined. In this model, parallel actions in macro-time are interleaving in micro-time. The mental state of Agent is constructed on macro-time, and the semantics of concurrent actions are given in micro-time level. Thus, it can be a proper logic basis for describing multi-Agent cooperation and competition that involve concurrent, and it can advance the work in Agent models developed by Rao & Georgeff, Singh and Werner et al.

Abstract:A geometrical representation of M-P model is firstly introduced, by which the training problem of neural networks may be transformed into the covering problem of a point set. According to this, the geometrical algorithm of neural network training is analyzed. The algorithm may be used for constructing very complicated classifying boundary, but it has higher time complexity. So a fuzzy classifier based on the combination of the covering approach and fuzzy set theory is proposed. The classifier can improve the speed of training and decrease the number of covering sphere-neighborhoods, i.e., decrease the number of hidden nodes of neural networks. The fuzzy set based approach may also provide multi-choices for pattern recognition problems of large scale. Recognition of 700 handwritten Chinese characters is used to test the performance of the approach and the results are promising.

Abstract:Text filtering is the procedure of retrieving documents relevant to the requirements of specific users from a large-scale text data stream. First, the TREC (text retrieval conference) as well as its text filtering track are introduced, which is the most authoritative international evaluation conference on text retrieval, from the aspects of tasks, topics, corpus and evaluation metrics. Then a text filtering system based on vector space model is presented. This system is composed of two phases of training and adaptive filtering. During the training phase, feature selection and pseudo feedback are used to select the initial filtering profiles and thresholds. During the filtering phase, user feedback is utilized to modify the profiles and thresholds adaptively. This system took participate in the 9th Text Retrieval Conference in 2000, and ranked high among all the 15 systems from many countries. Good performance has been achieved, where the average precisions of adaptive and batch filtering are 26.5% and 31.7% respectively.

Abstract:A distributed asynchronous parallel evolutionary modeling algorithm for solving the evolutionary modeling problem of system of ordinary differential equations is proposed in this paper. Performed on a simulated parallel environment consisting of 128 Pentium III 500 PCs connected by a 10Mbps Ethernet, large-scale experiments have been done to systematically test the effect of some important parallel control parameters, which include the degree of connectivity between processors, the migration rate and the migration interval of individuals, on the performance of the algorithm. Many new experimental results are achieved as well as some analysis and explanations are given. Especially the best modeling results for the sequential algorithm and the parallel one are compared at the end.

Abstract:Support vector machine is a new learning method developed in recent years based on the foundations of statistical learning theory. It is gaining popularity due to many attractive features and promising empirical performance in the fields of nonlinear and high dimensional pattern recognition. TSVM (transductive support vector machine) takes into account a particular test set and tries to minimize misclassifications of just those particular examples. Compared with traditional inductive support vector machines, TSVM is often more practical and can give results with better performance. In this paper, a progressive transductive support vector machine is devised and the experimental results show that the algorithm is very promising on a mixed training set of a small number of unlabeled examples and a large number of labeled examples.

Abstract:Visual information can improve speech perception. But how to synthesis the realistic mouth shape is a complex problem. After studying the rule of lip movement in speaking, a dominance blending dynamic viseme model for visual speech synthesis is proposed in this paper. Furthermore, considering the characteristic of Chinese speech, a systemic learning method is given to learn the model parameters from training data, which is more reliable than desire parameters according to subjective experience. Experimental results show that the dynamic viseme model and learning method are effective.

Abstract:As an adaptive algorithm of signal decomposition, matching pursuits provides a new framework for sinusoidal modeling of speech and audio signal. In this paper, the procedure of sinusoidal modeling using matching pursuits is analyzed as well as the sinusoidal modeling algorithm using perceptually weighted matching pursuits. And a method of sinusoidal modeling with perceptual gradient is proposed. The proposed method, which adopts the adaptive feature of matching pursuits, computes dynamically a masking threshold from the currently synthesized signal using the psychoacoustic model. With the threshold, it extracts the most perceptually significant component from the residual signal. Therefore, the perceptual information contained in the synthesized signal increases as quickly as possible. The quality of the synthesized speech by this approach is rather high even if the model precision is low. Experiments prove that the method in this paper uses the features of hearing system in a better way, and the modeling is reasonable and efficient. Both the objective compare of SNR and the subjective listening test show the rationality and superiority of the new method.

Abstract:As a novel system description and problem solving method, Agent organization can potentially decrease the difficulty of problem solving and reduce the complexity of Agent interactions. Current researches about Agent organization are mostly being undertaken in Agent organization model, organization rules, organization structure, organization formation and evolution, so it is necessary to extend the research to analyze mental states and their relations. In this paper, the mental states of commitments in Agent organization are defined and analyzed including internal commitment, social commitment, group commitment and organization commitment. The semantics and properties of different commitments are given so that the works associated with Agent organization can be advanced.

Abstract:In order to improve the predictive accuracy of inductive learning, a heavy analysis about the demerit of C4.5 is given, and the reason why there are many debates and compromise between standard method and meta algorithms is pointed out. By the method of estimating the probability distribution of training examples, a new and simple method of decision tree is turned out. Experimental results on UCI data sets show that the proposed method has good performance on accuracy issue and faster computing speed than C4.5 algorithm.

Abstract:Fingerprint enhancement is important for improving the accuracy of minutiae extraction, even for the total automated fingerprint identification system (AFIS). A fingerprint enhancement algorithm based on Gabor function and its application is developed in this paper. A method for ridge orientation acquirement is improved and a new method for ridge frequency acquirement is brought out. The formula that Gabor function is used in fingerprint enhancement is presented, and the fingerprint enhancement is implemented using ridge orientation and ridge frequency as parameters. The performance of this method is evaluated with some typical low quality images of Nanjing University fingerprint database. Experimental results indicate that the method has dramatic effect to low quality fingerprint images and false reject rate (FRR) of fingerprint matching can be effectively decreased after enhancement. Speed of the method can fill the demand of on-line AFIS.

Abstract:Considering the weaknesses of traditional serial feature fusion technique, a novel parallel features fusion method is proposed in this paper. The main idea of this method can be described as follows. First of all, two sets of feature vectors corresponding to a same sample space are combined together via complex vectors, which are used to construct a complex feature vector space. Then, the classical K-L transform and K-L expansion methods are developed theoretically to suit for feature extraction in the complex feature space. Moreover, the symmetric property of parallel feature fusion is revealed, and, how to combine features effectively is discussed in detail. Finally, the proposed method is used to solve the handwritten character feature extraction and recognition problems. Experiments are performed on NUST603 handwritten Chinese character database built in Nanjing University of Science and Technology as well as the well-known CENPARMI handwritten digit database of Concordia University. The experimental results indicate that the recognition rates are improved significantly after parallel feature fusion, and the proposed parallel features fusion method is superior to the traditional serial feature fusion one.

Abstract:Many services, including video conference, whiteboard and video broadcasting, have been running over LANs. However, most of LANs, such as Ethernet, treat multicast just as broadcast, and they all have few supports for multicast. In this paper, a multicast protocol in an LAN switch, named IGMP snooping, is implemented based on VLAN and IGMP. IGMP snooping will be applied to the IP multicast stream control on the switch Ethernet. The basic idea, syntax and semantics of this protocol are given in this paper, and the verification and test procedure is also provided.

Abstract:AQM (active queue management) can maintain the smaller queuing delay and higher throughput by the purposefully dropping the packets at the intermediate nodes. It is a hotspot in the current researches about TCP end-to-end congestion control. Almost all the existed algorithms neglect the impact on performance caused by large delay. In this study, firstly a fact through simulation experiments is verified, which is the queues controlled by several typical AQM algorithms, including RED, PI controller and REM, the dramatic oscillations in large delay networks are appeared, which decreases the utilization of the bottleneck link and introduces the avoidable delay jitter. After some appropriate model approximation, a robust AQM algorithm applying the principle of internal mode compensation in control theory is designed. The new algorithm restricts the negative impact on the queue stability caused by the large delay. The simulation experimental results show that the integrated performance of the proposed algorithm is obviously superior to that of the existed schemes when the network configuration parameters are large delay and small queue length, and the link utilization increases 3~4 times.

Abstract:The security evaluation of a class of block ciphers based on chaotic maps against differential and linear attacks is studied. If the round function is bijective and its maximum differential and linear characteristic probabilities are p and q respectively, the upper bounds of maximum differential and linear characteristic probabilities for r rounds are p^r-1and q^r-1 respectively.

Abstract:The analysis of security about TLS (transport layer security) protocol is proposed in this paper, based on once encipherment, access control and dual certificate. Upon the analysis, extensions are given for message process and content of TLS, the improved protocol is more secure and practical.

Abstract:With the growth of Internet, it becomes a challenging problem to test the running characteristics of routing protocol implementations in realistic large-scale networks. An Internet routing emulation system (IRES) is developed as a test bed to test and analyze the above characteristics. A novel approach by combining Internet topology generation and routing protocol implementation is proposed, and the architecture of IRES is presented. Then the Internet hierarchical topology is analyzed and a method is proposed to transform GT-ITM model to BGP-OSPF oriented Internet topology. In the given examples, by measuring the routing interaction with CISCO2600 router, its computation complexity of the OSPF protocol implementation in the CISCO2600 router is O((lgN)⁴), and the upper bound it supports is given. The experimental results show that as a test bed, IRES has an important role that cannot be replaced by others.

Abstract:Packet scheduling algorithm is an important element to provide quality of service (QoS) guarantee. Traditional per-flow packet scheduling methods are often not able to support good scalability. While, the non-per-flow-differentiated methods usually can not provide service guarantee for very individual flow. DPS (dynamic packet state) provides a method to support guaranteed service without per-flow control. It can provide both the service performance and scalability. But its per-packet scheduling results in high computational complex are related with the number of packets. A packet scheduling algorithm with multi-level FIFS queues, which is based on DPS, is provided in this paper to get guaranteed service. And the constrained conditions to delay guarantee under this algorithm is also provided. The theoretical analysis and simulations show that the algorithm can schedule packets with constant time complexity and the same delay performance as DPS.

Abstract:With the development of computer and network technologies and emerging of diverse types of terminal, the ability of network computing to tailor applications to the capabilities of heterogeneous client devices will realize its full potential at last. Most of the existing terminals first start OS locally and then load network-computing software. However, this booting way can’t satisfy the diversity of terminals and the increasing of complexity of network-computing software. A reliable, secure, effective and customizable remote boot protocol named as NCBP (network-based client boot protocol) is presented in this paper, which is hoped to increase the flexibility of existing network computing terminals’ booting process and thus increase the flexibility and availability of network computing. NCBP uses extended DHCP (dynamic host configuration protocol) to acquire local identifier, then loads a batch script language environment of MBatch (MenuBatch) by using secure APTP (active program transfer protocol). When executing the loaded MBatch script, NCBP allows users to select which OS to be loaded and then load the corresponding OS image in a customizable way. NCBP can be used for remote boot of network computers, PCs, and digital appliances.

Abstract:Labels are the foundation for implementing multilevel systems and the prerequisite of enforcing mandatory access control in secure systems. How to define and enforce label functions which support multiple security policies is the focus here. A security label common framework (SLCF) based on static object label and dynamic subject label is put forward. SLCF introduces the notation of access history and provides a complete label funtions set. Based on SLCF, both multilevel confidential policy and multilevel integrity policy can be expressed and enforced. SLCF is implemented in a secure operating system based on Linux, the experimental results show that the system based on SLCF is flexible and practicable.

Abstract:After analyzing and summarizing the main current research outcomes of IP multicast routing, a multicast routing algorithm called on-demand branching multicast is proposed. On-Demand branching multicast uses a new multicast tree maintenance method, in which the tree is maintained only by partial nodes or key nodes. That is different from the traditional methods in which the tree is maintained by all the nodes on the tree, and so as to save the Internet resources.

Abstract:Available bit rate (ABR) flow control is an effective measure in ATM network congestion control and traffic management. In high-speed ATM networks, the switch performance lies on the algorithm simplicity in some degree. Although the simplicity of binary flow control is very attractive, the queue length and allowed cell rate (ACR) controlled by the standard EFCI algorithm oscillate with great amplitude, which must have negative impact on the performance, so its applicability is doubted, and then the explicit rate feedback mechanism, which is relatively complex but effective, is introduced and explored. In this study, based on the ABR flow control model, a novel binary ABR flow control algorithm is put forward using the approach for designing the sliding mode variable structure controller in robust control theory, jointly applying the congestion detection mechanism based on the probability. The new algorithm avoids the self-oscillation induced by the nonlinear component in the standard EFCI algorithm, which is very favorable for utilizing the simplicity of binary flow control mechanism to optimize the switch performance. The simulation results show that the sliding mode variable structure controller greatly constrains the oscillations of ACR and queue, smoothes the delay jitter, which provides the reliable implementation mechanism for QoS guarantee in ATM network.

Abstract:The security of AC against differential and linear cryptanalysis is discussed in this paper. It is shown that 12-round AC has no differential characteristic with probability higher than 2-128 and no linear approximations with approximation bias larger than 2-67 by estimating the lower bound of the number of active-boxes in 3-round differential characteristic and 12-round linear approximation. Hence, AC is secure to differential and linear cryptanalysis.

Abstract:Routing and channel assignment is a key topic in optical interconnection networks, and it is a primary way to get insight into the capacity of interconnection networks. Based on the optical RP(k) network, the wavelength assignment of realizing the Hypercube communication with N=2n nodes on the optical RP(k) network is discussed. By defining the reverse order of the Hypercube, an algorithm to embed the n-D Hypercube into the RP(k) network is designed, which needs at most max{2,「5.2^n-5/3」} wavelengths. An algorithm to embed the n-D hypercube into the ring network is also proposed, with its congestion equal to 「N/3+N/12」. This is a better improvement than the known results, which is equal to 「N/3+N/4」. The two algorithms proposed in this paper are of great value in designing optical networks.