Fundamenta Informaticae - Volume 95, issue 2-3

Authors: Amirani, Mehdi Chehel | Shirazi, Ali Asghar Beheshti

Article Type: Research Article

Abstract: In this paper a new feature extraction technique for texture analysis is evaluated. This method is based on spectral correlation function (SCF) that provides a second-order statistical description in the frequency domain of signals. Two one dimensional signals are obtained from each image by ordering of pixels row by row and column by column. Then the SCF of each signal is calculated by a computational efficient algorithm, namely, the FFT accumulation method (FAM). Features are energy …and standard deviation of spectral correlation functions at different regions of bifrequency planes. This scheme shows high performance in the retrieval and classification of Brodatz texture images. Experimental results indicate that the proposedmethod improves retrieval accuracy and correct classification rate in comparing with other approaches. Furthermore the evaluation of the hidden layer output at the classifier with different numbers of neurons indicates that the extracted features from SCF are more separable potentially in comparing with traditional discrete wavelet transform approaches. Show more

Keywords: Texture analysis, Texture classification, Texture retrieval, Spectral correlation function, Feature extraction

DOI: 10.3233/FI-2009-149

Citation: Fundamenta Informaticae, vol. 95, no. 2-3, pp. 245-262, 2009

Authors: Byrski, Aleksander | Schaefer, Robert

Article Type: Research Article

Abstract: The mathematical model of the biologically inspired, memetic, agent-based computation systems EMAS and iEMAS conformed to BDI standard is presented. The state of the systems and their dynamics are expressed as stationary Markov chains. Such an approach allows to better understand their complex behavior as well as their limitations.

Keywords: Multi-agent systems, agent-based computation, stochastic modeling

DOI: 10.3233/FI-2009-150

Citation: Fundamenta Informaticae, vol. 95, no. 2-3, pp. 263-285, 2009

Authors: Finkel, Olivier | Simonnet, Pierre

Article Type: Research Article

Abstract: We investigate the topological complexity of non Borel recognizable tree languages with regard to the difference hierarchy of analytic sets. We show that, for each integer n ⩾ 1, there is a D_{&omega;^n} (Σ^1_1 )-complete tree language L_n accepted by a (non deterministic) Muller tree automaton. On the other hand, we prove that a tree language accepted by an unambiguous Büchi tree automaton must be Borel. Then we consider the game tree …languages W_{(&inodot;,&kappa;)} , for Mostowski-Rabin indices (ıκ). We prove that the D_{&omega;^n} (Σ^1_1 )-complete tree languages L_n are Wadge reducible to the game tree language W_{(&inodot;,&kappa;)} for κ−ı⩾ 2. In particular these languages W_{(&inodot;,&kappa;)} are not in any class D_{&alpha;} (Σ^1_1 ) for α<ω^{&omega;} . Show more

Keywords: Infinite trees, tree automaton, regular tree language, Cantor topology, topological complexity, Borel hierarchy, difference hierarchy of analytic sets, complete sets, unambiguous tree automaton, game tree language

DOI: 10.3233/FI-2009-151

Citation: Fundamenta Informaticae, vol. 95, no. 2-3, pp. 287-303, 2009

Authors: Mirkowska, Grażyna | Salwicki, Andrzej | Świda, Oskar

Article Type: Research Article

Abstract: The problem of correctness of a class C w.r.t. a specification S is discussed. A formal counterpart of the problem is the question well known in metamathematics, whether an algebraic structure is a model of a given theory. Now, this metamathematical problem has to be adapted to the context of software engineering. As a theory we consider the (algorithmic) specification S. The algebraic structure A_C induced by the class C is our candidate for a model of …S. Remark, that this problem differs from the correctness' problem of an algorithm w.r.t. a pre- and a post-conditions. In the paper we consider the specification ATPQ of priority queues and the class PQS, and we verify the correctness of this class with respect to the specification ATPQ. Programmers and software companies prefer to test software instead of proving it. Surely, proving is more difficult, testing is easier. In this article we combine these two approaches. Hence, the following actions appear in our method of verification: experiment, observe, formulate hypotheses, prove. It is our hope that this method is of general use and adapts well to many practical cases of verification of object-oriented software. Show more

DOI: 10.3233/FI-2009-152

Citation: Fundamenta Informaticae, vol. 95, no. 2-3, pp. 305-324, 2009

Authors: Schaefer, Robert | Byrski, Aleksander | Smołka, Maciej

Article Type: Research Article

Abstract: The refined model for the biologically inspired agent-based computation systems EMAS and iEMAS conforming to the BDI standard is presented. Moreover, their evolution is expressed in the form of the stationary Markov chains. This paper generalizes the results obtained by Byrski and Schaefer [7] to a strongly desired case in which some agents' actions can be executed in parallel. In order to find the Markov transition rule, the precise synchronization scheme was introduced, which allows to …establish the stepwise stochastic evolution of the system. The crucial feature which allows to compute the probability transition function in case of parallel execution of local actions is the commutativity of their transition operators. Some abstract conditions expressing such a commutativity which allow to classify the agents' actions as local or global are formulated and verified in a very simple way. The above-mentioned Markov model constitutes the basis of the asymptotic analysis of EMAS and iEMAS necessary to evaluate their search possibilities and efficiency. Show more

Keywords: Multi-agent systems, agent-based computation, stochastic modeling

DOI: 10.3233/FI-2009-153

Citation: Fundamenta Informaticae, vol. 95, no. 2-3, pp. 325-348, 2009

Authors: Trojanowski, Krzysztof

Article Type: Research Article

Abstract: This paper studies properties of a multi-swarm system based on a concept of physical quantum particles (mQSO). Quantum particles differ from the classic ones in the way they move. As opposed to the classic view of particle movement, where motion is controlled by linear kinematic laws, quantum particles change their location according to random distributions. The procedure for generating a new location for the quantum particle is similar to mutation operators widely used in evolutionary computation …with real-valued representation. In this paper we study a set of new distributions of candidates for quantum particle location, and we show different features of these distributions. The distributions considered in this paper are divided into two classes: those with a limited range of the new location coordinates and those without such limitations. They are tested on different types of dynamic optimization problems. Experimental verification has been based on a number of testing environments and two main versions of the algorithm: with and without mechanisms protecting against stagnation caused by convergence of sub-swarms during the search process. The experimental results show the advantages of the distribution class, in which the candidates are spread out in the entire search space, and indicate the positive and negative aspects of application of anti-convergencemechanisms. Show more

Keywords: optimization in dynamic environments, particle swarm optimization, tracking optima in dynamic environments, multi-swarm, quantum particles

DOI: 10.3233/FI-2009-154

Citation: Fundamenta Informaticae, vol. 95, no. 2-3, pp. 349-380, 2009

Authors: Vágvölgyi, Sándor

Article Type: Research Article

Abstract: We show that it is decidable for any extended ground term rewrite system R whether there is a ground term rewrite system S such that the congrunce ↔^*_R generated by R is equal to the congruence ↔^*_S generated by S. If the answer is yes, then we can effectively construct such a ground term rewrite system S. We characterize congruences generated by extended ground term rewrite systems.

Keywords: Extended ground term rewrite system, tree automaton

DOI: 10.3233/FI-2009-155

Citation: Fundamenta Informaticae, vol. 95, no. 2-3, pp. 381-399, 2009