The main idea of filter methods in feature selection is constructing a feature-assessing criterion and searching for feature subset that optimizes the criterion. The primary principle of designing such criterion is to capture the relevance between feature subset and the class as precisely as possible. It would be difficult to compute the relevance directly due to the computation complexity when the size of feature subset grows. As a result, researchers adopt approximate strategies to measure relevance. Though these strategies worked well in some applications, they suffer from three problems: parameter determination problem, the neglect of feature interaction information and overestimation of some features. We propose a new feature selection algorithm that could compute mutual information between feature subset and the class directly without deteriorating computation complexity based on the computation of partitions. In light of the specific properties of mutual information and partitions, we propose a pruning rule and a stopping criterion to accelerate the searching speed. To evaluate the effectiveness of the proposed algorithm, we compare our algorithm to the other five algorithms in terms of the number of selected features and the classification accuracies on three classifiers. The results on the six synthetic datasets show that our algorithm performs well in capturing interaction information. The results on the thirteen real world datasets show that our algorithm selects less yet better feature subset.

One of the most important problems in web services application is the integration of different existing services into a new composite service. Existing work has the following disadvantages: (i) developers are often required to provide a composite service model first and perform formal verifications to check whether the model is correct. This makes the synthesis process of composite services semi-automatic, complex and inefficient; (ii) there is no assurance that composite services synthesized by using the fully-automatic approaches are correct; (iii) some approaches only handle simple composition problems where existing services are atomic. To address these problems, we propose a correct assurance approach for automatically synthesizing composite services based on finite state machine model. The syntax and semantics of the requirement model specifying composition requirements is also proposed. Given a set of abstract BPEL descriptions of existing services, and a composition requirement, our approach automatically generate the BPEL implementation of the composite service. Compared with existing approaches, the composite service generated by utilizing our proposed approach is guaranteed to be correct and does not require any formal verification. The correctness of our approach is proved. Moreover, the case analysis indicates that our approach is feasible and effective.

Formalizing requirements in formal specifications is an effective way to deepen the understanding of the envisioned system and reduce ambiguities in the original requirements. However, it requires mathematical sophistication and considerable experience in using formal notations, which remains a challenge to many practitioners. To handle this challenge, this paper describes a pattern-based approach to facilitate the formalization of requirements. In this approach, a pattern system is pre-defined to guide requirements formalization where each pattern provides a specific solution for formalizing one kind of function into a formal expression. All of the patterns are classified and organized into a hierarchical structure according to the functions they can be used to formalize. The distinct characteristic of our approach is that all of the patterns are stored on computer as knowledge for creating effective guidance to facilitate the developer in requirements formalization; they are “understood” only by the computer but transparent to the developer. We also describe a prototype tool that supports the approach. It adopts Hierarchical Finite State Machine (HFSM) to represent the pattern knowledge and implements an algorithm for applying it to assist requirements formalization. Two experiments on the tool are presented to demonstrate the effectiveness of the approach.

Since scan testing is not based on the function of the circuit, but rather the structure, it is considered to be both a form of over testing and under testing. Moreover, it is important to test VLSIs using the given function. Since the functional specifications are described explicitly in the FSMs, high test quality is expected by performing logical fault testing and timing fault testing. This paper proposes a fault-dependent test generation method to detect specified fault models completely and to increase defect coverage as much as possible under the test length constraint. We present experimental results for MCNC'91 benchmark circuits to evaluate bridging fault coverage, transition fault coverage, and statistical delay quality level and to show the effectiveness of the proposed test generation method compared with a stuck-at fault-dependent test generation method.

In this paper, we investigate a low-power architecture for designs modeled as an Extended Finite State Machine (EFSM). It is based on the general dynamic power management concept, in which the redundant computation can be dynamically disabled to reduce the overall power dissipation. The contribution of this paper is mainly a systematic procedure to identify almost maximal amount of redundant computation in a design given as an EFSM. There are two levels of redundant computation to be exploited--one is based on the machine state information, while the other is based on the transition information. After the extraction of the redundant computation, a low-power architecture using input gating is proposed to synthesize the final circuit. We tested the technique on a design computing a number's modulo inverse. Experimental results show that 31% power reduction can be achieved at the costs of 2% timing penalty and 16% area overhead.

In the Internet, flow analysis and network monitoring have been studied by various methods. Some methods try to make TCP (Transport Control Protocol) traces more readable by showing them graphically. Others such as MRTG, NetScope, and NetFlow read the traffic counters of the routers and record the data for traffic engineering. Even if all of the above methods are useful, they are made only to perform a single task. This paper describes an improved TCP Protocol Machine, a multipurpose tool that can be used for flow analysis, intrusion detection and link congestion monitoring. It is developed based on a finite state machine (automaton). The machine separates the flows into two main groups. If a flow can be mapped to a set of input symbols of the automaton, it is valid, otherwise it is invalid. It can be observed that intruders' attacks are easily detected by the use of the protocol machine. Also link congestion can be monitored, by measuring the percentage of valid flows to the total number of flows. We demonstrate the capability of this tool through measurement and working examples.

In this paper, we propose an algorithm to convert a given structured LOTOS specification into an equivalent flattened model called synchronous EFSMs. The synchronous EFSMs model is an execution model for communication protocols and distributed systems where each system consists of concurrent EFSMs and a finite set of multi-rendezvous indications among their subsets. The EFSMs can be derived from a specification in a sub-class of LOTOS and its implementation becomes simpler than the straightforward implementation of the original LOTOS specification because the synchronization among the processes in the model does not have any child-parent relationships, which can make the synchronization mechanism much more complex. Some experimental results are reported to show the advantage of synchronous EFSMs in terms of execution efficiency.

In this paper, we propose a technique to synthesize a hardware circuit from a protocol specification consisting of several concurrent EFSMs with multi-rendezvous specified among their subsets. In our class, each multi-rendezvous can be specified among more than two EFSMs, and several multi-rendezvous can be specified for different combinations of EFSMs. In the proposed technique, using the information such as current states of EFSMs, input values at external gates and guard expressions, we compose a circuit to evaluate whether each multi-rendezvous can be executed. If several exclusive multi-rendezvous get executable simultaneously for some combinations of EFSMs, we select one of them according to the priority order given in advance. We compose such a circuit as a combinational logic circuit so that it works fast. By applying our technique to Abracadabra protocol specified in LOTOS, it is confirmed that the derived circuit handles multi-rendezvous efficiently.

This paper presents an effective application of Net-theory for all the stages of the communication protocol development process. Net-theory provides a basic mathematical model and tool for development of communication protocol. The special usability of Net-theory is that 1) visual representation of the system's stadic/dynamic structure, so that users may easily understand the represented contents, 2) formal specifications based on mathematical basis of Net-theory admit automatic verification, implementation and conformance testing. We have seen that Net-theory which has the above usability can provide a systematic and advanced paradigm for effective communication protocol development.

This paper surveys modeling techniques for telephone call control based on a Finite State Machine (FSM) concept, and studies model simplification techniques. First, the basic concept and fundamental issues of call control modeling are described. Then, based on the analysis of layered call control configuration, it is clarified that the call control machine decomposition within the two-party service control layer has the effect of reducing the apparent size of each mate's machine. Using this effect, guidelines for call control modeling are derived, by which multiple services can be modeled independently. Finally implementation techniques and a few examples of application will be presented.