Vol. 29 · No. 6+

Automatic synthesis of control for a kind of DES (discrete-event systems) is discussed and an approach to it is proposed and presented. The approach consists in the proposal of the control synthesis procedure based on bipartite directed graphs yielding both the feasible control trajectories and the corresponding state ones. Soundness of the approach is tested on examples. Then, the usage of the approach is combined with the supervisor synthesis in order to complement it. Applicability of such approach is demonstrated by means of several illustrative examples of both the single agents and the agent cooperation in MAS.

The paper presents conditions of extension of the weakly defined Boolean functions to their full affine form. The main goal of the analysis is a fast estimation whether a given incompletely defined function can be extended to a full affine form. If it is possible a simple algorithm of the states completion has been proposed. In such a case undefined points are clearly replaced by 0, 1 values. Spectral coefficients of a Boolean function allow to determine whether a partially defined function can be realised as affine.

Intrusion detection is used to monitor and capture intrusions into computer and network systems which attempt to compromise their security. Many intrusions manifest in dramatic changes in the intensity of events occuring in computer networks. Because of the ability of exponentially weighted moving average control charts to monitor the rate of occurrences of events based on their intensity, this technique is appropriate for implementation in threshold based algorithms.

Program can be viewed as a sequence of statements that are aimed to produce some result. The execution is done by a platform that interprets the program sequence of statements. The new result of a computation can be achieved by modification of a program, a language interpreter, or both. Software evolution as long-term process can be supported by adaptive language and by environment, which offers reflective possibilities. This paper presents our adaptive approach to both program and language modification in order to support dynamic evolution. Effective software evolution needs to be supported by appropriate execution environment. We have proposed such experimental execution environment, which allows both run-time program and language modification. As we hope, mutating a programming language to a higher abstraction may decrease structural complexity of programs in the future.

Mobile grid computing is aimed at making grid services available and accessible anytime anywhere from mobile device; at the same time, grid users can exploit the limited resources of mobile devices. This paper proposes simultaneous optimization of application utility and consumed energy in mobile grid. The paper provides a comprehensive utility function, which optimizes both the application level satisfaction such as execution success ratio and the system level requirements such as high resource utilization. The utility function models various aspects of job, application and system. The goal of maximizing the utility is achieved by decomposing the problem into a sequence of sub-problems that are then solved using the NUM optimization framework. The proposed price-based iterative algorithms enable the sub-problems to be processed in parallel. The simulations and analysis are given to study the performance of the algorithm.

This paper presents digital board games built upon RFID-based platforms. The platforms consist of RFID tag-embedded physical objects and RFID reader boards. A library is built upon the platforms for recognizing data, locations, and movements of the physical game objects. Three kinds of game prototypes are designed and developed for use in young children's edutainment. The user tests prove that a natural type of interactivity can be achieved for digital board games, and it can contribute to establishing paradigms for next-generation edutainment.

The search process is critical for iterative compilation because the large size of the search space and the cost of evaluating the candidate implementations make it infeasible to find the true optimal value of the optimization parameter by brute force. Considering it as a nonlinear global optimization problem, this paper introduces a new hybrid algorithm – UMDA/S: Univariate Marginal Distribution Algorithm with Nelder-Mead Simplex Search, which utilizes the optimization space structure and parameter dependency to find the near optimal parameter. Elitist preservation, weighted estimation and mutation are proposed to improve the performance of UMDA/S. Experimental results show the ability of UMDA/S to locate more excellent parameters, as compared to existing static methods and search algorithms.

This paper presents an empirical study of non-preemptive Multicriteria-Based, called MCB for short, scheduling policy. MCB scheduling policy uses multiple criteria of each request: arrival time, deadline, and processing time, to balance the requirements on both client and server sites. Weighted aggregation method is applied in this study to conduct the different measurements to a single figure of merit. For the empirical study, an M/G/1 queuing simulation system is implemented with MATLAB to represent a general server's incoming request scheduling system. Comparative simulation results of MCB with best effort scheduling policy on an overload situation show that MCB is an optimal scheduling policy.

Data streaming applications bring new challenges to resource management and scheduling for grid computing. Since real-time data streaming is required as data processing is going on, integrated grid resource management becomes essential among processing, storage and networking resources. Traditional scheduling approaches may not be sufficient for such applications, since usually only one aspect of grid resource scheduling is focused. In this work, an integrated resource scheduling approach is proposed and coordinated resource allocation of CPU cycles, storage capability and network bandwidth is implemented. Resource allocation is performed periodically with updated information on resources and applications and heuristic search for optimal solutions is used to assign various resources for running applications simultaneously. Performance metrics considered in this work include data throughput and utilization of processors, storage, and bandwidth, which are actually tightly coupled with each other when applied for grid data streaming applications. Experimental results show dramatic improvement of performance and scalability using our implementation.

Visualization of a large-scale protein databases may help biologists in discovering similarity between sequences of different organisms. In this article we present a complex approach for visually representing relations between proteins in large scale databases. Our approach includes sequence alignment, mutual distance measurement, clustering and classification of protein sequences. We propose a visual representation method for considered as well-established Pfam 4.0 proteins database. Our objective is to visually reflect the similarity of protein sequences in three dimensional space using nonstandard approach.

Multiple sequence alignment is a central topic of extensive research in computational biology. Basically, two or more protein sequences are compared to evaluate their similarity and to identify conserved regions. This work reports a methodology for parallel processing of a multiple sequence alignment algorithm (ClustalW) in an environment of networked computers. A detailed description of the modules that compose the distributed system is provided, giving special attention to the way a dynamic programming algorithm is run in multilevel parallelism. Extensive experiments were done to evaluate performance and scalability of the reported method. Results suggest that the proposed method is very promising for large-scale multiple protein sequence alignment.

In this paper an evolutionary approach to solving the generalized vertex cover problem (GVCP) is presented. Binary representation and standard genetic operators are used along with the appropriate objective function. The experiments were carried out on randomly generated instances with up to 500 vertices and 100 000 edges. Performance of the genetic algorithm (GA) is compared with CPLEX solver and 2-approximation algorithm based on LP relaxation. The genetic algorithm outperformed both CPLEX solver and 2-approximation heuristic.

Multiple description coding (MDC) is a promising alternative to combatting information loss without any retransmission. In this paper, an effective MD video codec is designed based on temporal pre- and post-processing of video sequences without modifying the actual coding process itself, which makes it compatible with the current standard source or channel codec. For ease of post-processing, motion-compensated interpolation (MCI) based on piecewise uniform motion assumption is adopted to estimate the lost frame in side decoding. Accordingly, to match the post-processing, in the pre-processing joint frame duplication/interpolation is first applied to the original video data before performing odd/even frame splitting, which attempts to make the motion variety in the generated descriptions piecewise uniformly thus achieving better side reconstructed quality based on MCI. The experimental results exhibit better performance of the proposed scheme than some other tested schemes, in both the on-off channel environment and packet loss network.

Service discovery constructs a bridge between the service providers and the service consumers, and is a key point in pervasive computing environments. In group-based service discovery protocols, selective forwarding service requests only based on the service group maybe lead to unnecessary forwarding, which produces large packet redundancy. This paper proposes an efficient service discovery protocol: SIGIFSDP (Service Id Guided Intelligent Forwarding Service Discovery Protocol). In SIGIFSDP, based on GSD, SIGIF (Service Id Guided Intelligent Forwarding) is introduced to select the exact forwarding nodes based on the service id. Theoretical analysis and simulation results using GloMosim verify that SIGIFSDP can save the response time, reduce the service request packets, and improve the efficiency of service discovery.

We extend the usual notion of Kripke structures with a weighted transition relation and generalize the classical Boolean interpretation of CTL to a map which assigns to states and temporal formulae a real-valued distance describing the degree of satisfaction. We describe a general approach to obtaining quantitative interpretations for a generic extension of the CTL syntax and show that, for one such interpretation, the logic is both adequate and expressive with respect to quantitative bisimulation.

The AutoDock suite is widely used molecular docking software consisting of two main programs – AutoGrid for precomputation of potential grid maps and AutoDock for docking into potential grid maps. In this paper, the acceleration of potential maps generation based on AutoGrid and its implementation called FastGrid is presented. The most computationally expensive algorithms are accelerated using GPU, the rest of algorithms run on CPU with asymptotically lower time complexity that has been obtained using more sophisticated data structures than in the original AutoGrid code. Moreover, the CPU implementation is parallelized to fully exploit computational power of machines that are equipped with more CPU cores than GPUs. Our implementation outperforms original AutoGrid more than 400 times for large, but quite common molecules and sufficiently large grids.

When comparing the fastest algorithm for computing the largest simulation preorder over Kripke structures with the one for labeled transition systems (LTS), there is a noticeable time and space complexity blow-up proportional to the size of the alphabet of an LTS. In this paper, we present optimizations that suppress this increase of complexity and may turn a large alphabet of an LTS to an advantage. Our experimental results show significant speed-ups and memory savings. Moreover, the optimized algorithm allows one to improve asymptotic complexity of procedures for computing simulations over tree automata using recently proposed algorithms based on computing simulation over certain special LTS derived from a tree automaton.

In this paper, we consider variants of a new problem that we call minimum Steiner cycle problem (SCP). The problem is defined as follows. Given is a weighted complete graph and a set of terminal vertices. In the SCP problem, we are looking for a minimum-cost cycle that passes through every terminal exactly once and through every other vertex of the graph at most once. We show that, if P neq NP, there is no approximation algorithm for SCP on directed graphs with an approximation ratio polynomial in the input size. Moreover, this result holds even in the case when the number of terminals is 4. On the contrary, we show that SCP on undirected graphs with constant number of terminals and edge costs satisfying the relaxed triangle inequality is approximable with the ratio beta2+ beta. When the number of terminals k is a part of the input, the problem is obviously a generalization of TSP. For the metric case, we present a frac32- and a frac23łog 2 k-approximation algorithm for undirected and directed graphs G=(V,E), respectively. For the case with the relaxed triangle inequality, we present a ( beta2+ beta)-approximation algorithm.

A new accelerator of Cartesian genetic programming is presented in this paper. The accelerator is completely implemented in a single FPGA. The proposed architecture contains multiple instances of virtual reconfigurable circuit to evaluate several candidate solutions in parallel. An advanced memory organization was developed to achieve the maximum throughput of processing. The search algorithm is implemented using the on-chip PowerPC processor. In the benchmark problem (image filter evolution) the proposed platform provides a significant speedup (170) in comparison with a highly optimized software implementation. Moreover, the accelerator is 8 times faster than previous FPGA accelerators of image filter evolution.