Vol. 29 · No. 3

Systems composed of several interacting autonomous agents have a huge potential to efficiently address complex real-world problems. Usually agents communicate by directly exchanging information and knowledge about the environment. The aim of the paper is to develop a new computational model that endows agents with a supplementary interaction/search mechanism of stigmergic nature. Multi-agent systems can therefore become powerful techniques for addressing NP-hard combinatorial optimization problems. In the proposed approach, agents are able to indirectly communicate by producing and being influenced by pheromone trails. Each stigmergic agent is characterized by a certain level of sensitivity to the pheromone trails. The non-uniform pheromone sensitivity allows various types of reactions to a changing environment. For efficient search diversification and intensification, agents can learn to modify their sensitivity level according to environment characteristics and previous experience. The resulting system for solving complex problems is called Learning Sensitive Agent System (LSAS). The proposed LSAS model is used for solving several NP-hard problems such as the Asymmetric and Generalized Traveling Salesman Problems. Numerical experiments indicate the robustness and the potential of the new metaheuristic.

In this paper we engage in AWGN watermark for grayscale image (the message is embedded by adding of white Gaussian noise matrix; detection is blind, correlation based). We search criteria for ``the best'' (minimal one which guaranties watermark detectability) embedding strength for watermark robust against expected attack. These criteria we find for AWGN watermarks, which are embedded in spatial or in transform domains; for one bit message or for a longer message; into whole image or into some of its coefficients. This paper peculiarity is that we do not propose new watermarking algorithm; for well known, robust algorithm we find the best embedding strength for robust watermark.

The multiagent workflow systems can be formalized from an organizational structure viewpoint, which includes three parts: the interaction structure among agents, the temporal flow of activities, and the critical resource sharing relations among activities. While agents execute activities, they should decide their strategies to satisfy the constraints brought by the organizational structure of multiagent workflow system. To avoid collisions in the multiagent workflow system, this paper presents a method to determine social laws in the system to restrict the strategies of agents and activities; the determined social laws can satisfy the characteristics of organization structures so as to minimize the conflicts among agents and activities. Moreover, we also deal with the social law adjustment mechanism for the alternations of interaction relations, temporal flows, and critical resource sharing relations. It is proved that our model can produce useful social laws for organizational structure of multiagent workflow systems, i.e., the conflicts brought by the constraints of organization structure can be minimized.

This paper considers verification of the liveness property textsfLive(R, I, G) for a term rewrite system (TRS) R, where I (Initial states) and G (Good states) are two sets of ground terms represented by finite tree automata. Considering I and G, we transform R to a new TRS R' such that termination of R' proves the property textsfLive(R, I, G).

The problem of finding a constrained longest common subsequence (CLCS) for the sequences A and B with respect to sequence P was introduced recently. Its goal is to find a longest subsequence C of A and B such that P is a subsequence of C. There are several algorithms solving the CLCS problem, but there is no real experimental comparison of them. The paper has two aims. Firstly, we propose an improvement to the algorithms by Chin et al. and Deorowicz based on an entry-exit points technique by He and Arslan. Secondly, we compare experimentally the existing algorithms for solving the CLCS problem.

In this paper, we propose a learning automata-based iterative algorithm for approximating a near optimal solution to the vertex coloring problem. Vertex coloring is a well-known NP-hard optimization problem in graph theory in which each vertex is assigned a color so that no two adjacent vertices have the same color. Each iteration of the proposed algorithm is subdivided into several stages, and at each stage a subset of the uncolored non adjacent vertices are randomly selected and assigned the same color. This process continues until no more vertices remain uncolored. As the proposed algorithm proceeds, taking advantage of the learning automata the number of stages per iteration and so the required number of colors tends to the chromatic number of the graph since the number of vertices which are colored at each stage is maximized. To show the performance of the proposed algorithm we compare it with several existing vertex coloring algorithms in terms of the time and the number of colors required for coloring the graphs. The obtained results show the superiority of the proposed algorithm over the others.

In this paper, we propose a new multi-comparand associative machine (MCA-machine) and its application to relational algebra operations. We first offer a new efficient associative algorithm for the multi-comparand parallel search. It generalizes the Falkoff associative algorithm that performs a parallel search in a matrix based on the exact match with a given pattern. Then we apply the new associative algorithm to implement one group of the relational algebra operations on the MCA-machine. Then, we propose efficient associative algorithms for implementing another group of the relational algebra operations. The proposed algorithms are represented as corresponding procedures for the MCA-machine. We prove their correctness and evaluate their time complexity.

Present speech recognition systems are becoming more complex due to technology advances, optimizations and special requirements such as small computation and memory footprints. Proper handling of system failures can be seen as a kind of fault diagnosis. Motivated by the success of decision tree diagnosis in other scientific fields and by their successful application in speech recognition in the last decade, we contribute to the topic mainly in terms of comparison of different types of decision trees. Five styles are examined: CART (testing three different splitting criteria), C4.5, and then Minimum Message Length (MML), strict MML and Bayesian styles decision trees. We apply these techniques to data of computer speech recognition fed by intrinsically variable speech. We conclude that for this task, CART technique outperforms C4.5 in terms of better classification for ASR failures.