Fundamenta Informaticae - Volume 69, issue 3

Authors: Bandini, Stefania | Mauri, Giancarlo | Vizzari, Giuseppe

Article Type: Research Article

Abstract: The aim of this paper is to describe algorithms and structures required to support action-at-a-distance in Situated Cellular Agents (SCA). This model provides the possibility to define heterogeneous entities placed in regular or irregular spatial infrastructures. Different mechanisms supporting field diffusion within these structures will be described and analyzed, with reference to their performance. A sample application of SCA model (a variation of Conway's Game of Life) will also be illustrated, while a more complex usage …of action-at-a-distance for pedestrian simulation will be sketched. Show more

Keywords: Multi agent systems, action-at-a-distance, diffusion

Citation: Fundamenta Informaticae, vol. 69, no. 3, pp. 251-271, 2006

Authors: Dereniowski, Dariusz | Kubale, Marek

Article Type: Research Article

Abstract: In this paper we deal with the problem of finding an optimal query execution plan in database systems. We improve the analysis of a polynomial-time approximation algorithm due to Makino et al. for designing query execution plans with almost optimal number of parallel steps. This algorithm is based on the concept of edge ranking of graphs. We use a new upper bound for the edge ranking number of a tree to derive a better worst-case performance …guarantee for this algorithm. We also present some experimental results obtained during the tests of the algorithm on random graphs in order to compare the quality of both approximation ratios on average. Both theoretical analysis and experimental results indicate the superiority of our approach. Show more

Keywords: edge ranking, performance guarantee, query processing, spanning tree

Citation: Fundamenta Informaticae, vol. 69, no. 3, pp. 273-285, 2006

Authors: Gerla, B. | Leuştean, I.

Article Type: Research Article

Abstract: Similarities are an extension of equivalence relations to a fuzzy context. In this paper we introduce the class of similarity MV-algebras obtained as a generalization of the variety of MV-algebras by adding a binary operator playing the role of similarity. We further introduce the similarity Łukasiewicz logic and we prove a completeness theorem.

Keywords: Many-valued logic, MV-algebras, similarities

Citation: Fundamenta Informaticae, vol. 69, no. 3, pp. 287-300, 2006

Authors: Kaminski, Michael | Tan, Tony

Article Type: Research Article

Abstract: In this paper we introduce a notion of a regular expression over infinite alphabets and show that a language is definable by an infinite alphabet regular expression if and only if it is accepted by finite-state unification based automaton – a model of computation that is tightly related to other models of automata over infinite alphabets.

Keywords: Finite state automata, infinite alphabets, regular expressions

Citation: Fundamenta Informaticae, vol. 69, no. 3, pp. 301-318, 2006

Authors: Wang, Ching-Lin | Hwang, Ren-Hung | Chan, Yung-Kuan | Chen, Chih-Ya | Cheng, Chuan-Chung

Article Type: Research Article

Abstract: Two different objects can be generally distinguished by their colors, areas, and perimeters. This paper hence proposes an image retrieval system which uses the colors, areas, and perimeters of objects in an image as the features of the image. The system is insensitive to the shift and rotation variations of objects in images, as well as to the scale and noise variations of images. The experimental results show that this system is capable of recognizing different …images very well. Show more

Keywords: image retrieval, color-based image retrieval, color attribute, color histogram

Citation: Fundamenta Informaticae, vol. 69, no. 3, pp. 319-330, 2006

Authors: Liu, Gui-Long

Article Type: Research Article

Abstract: The theory of rough sets deals with the approximation of an arbitrary subset of a universe by two definable or observable subsets called, respectively, the lower and the upper approximation. There are at least two methods for the development of this theory, the constructive and the axiomatic approaches. The rough set axiomatic system is the foundation of rough sets theory. This paper proposes a new matrix view of the theory of rough sets, we start with …a binary relation and we redefine a pair of lower and upper approximation operators using the matrix representation. Different classes of rough set algebras are obtained from different types of binary relations. Various classes of rough set algebras are characterized by different sets of axioms. Axioms of upper approximation operations guarantee the existence of certain types of binary relations (or matrices) producing the same operators. The upper approximation of the Pawlak rough sets, rough fuzzy sets and rough sets of vectors over an arbitrary fuzzy lattice are characterized by the same independent axiomatic system. Show more

Keywords: Rough Sets, Rough Fuzzy Sets, Axiomatic Systems of Rough Sets, Fuzzy Lattices, Approximation Operators

Citation: Fundamenta Informaticae, vol. 69, no. 3, pp. 331-342, 2006

Authors: Suraj, Zbigniew | Delimata, Pawel

Article Type: Research Article

Abstract: The objective of this study is to introduce a new model of data classification based on preliminary reduction of the training set of examples (preprocessing) in order to facilitate the use of nearest neighbours (NN) techniques in near real-time applications. This study accordingly addresses the issue of minimising the computational resource requirements of NN techniques, memory as well as time. The approach proposed in the paper is a modification of the classical k-Nearest Neighbours (k-NN) method …and the k-NN method with local metric induction. Generally, the k-NN method with local metric induction in comparison with the classical k-NN method gives better results in the classification of new examples. Nevertheless, for the large data sets the k-NN method with local metric induction is less time effective than the classical one. The time/space efficiency of classifying algorithms based on these two methods depends not only on a given metric but also on the size of training data. In the paper, we present three methods of preliminary reduction of the training set of examples. All reduction methods decrease the size of a given experimental data preserving the relatively high classification accuracy. Results of experiments conducted on well known data sets, demonstrate the potential benefits of such reduction methods. Show more

Keywords: k-NN method, preprocessing, local metric induction, reduction, classifier, weighted SVDM

Citation: Fundamenta Informaticae, vol. 69, no. 3, pp. 343-358, 2006