Fundamenta Informaticae - Volume 77, issue 3

Authors: Badouel, Eric | Chenou, Jules | Guillou, Goulven

Article Type: Research Article

Abstract: The firing rule of Petri nets relies on a residuation operation for the commutative monoid of non negative integers. We identify a class of residuated commutative monoids, called Petri algebras, for which one can mimic the token game of Petri nets to define the behaviour of generalized Petri nets whose flow relations and place contents are valued in such algebraic structures. The sum and its associated residuation capture respectively how resources within places are produced and …consumed through the firing of a transition. We show that Petri algebras coincide with the positive cones of lattice-ordered commutative groups and constitute the subvariety of the (duals of) residuated lattices generated by the commutative monoid of non negative integers. We however exhibit a Petri algebra whose corresponding class of nets is strictly more expressive than the class of Petri nets. More precisely, we introduce a class of nets, termed lexicographic Petri nets, that are associated with the positive cones of the lexicographic powers of the additive group of real numbers. This class of nets is universal in the sense that any net associated with some Petri algebra can be simulated by a lexicographic Petri net. All the classical decidable properties of Petri nets however (termination, covering, boundedness, structural boundedness, accessibility, deadlock, liveness ...) are undecidable on the class of lexicographic Petri nets. Finally we turn our attention to bounded nets associated with Petri algebras and show that their dynamics can be reformulated in term of MV-algebras. Show more

Citation: Fundamenta Informaticae, vol. 77, no. 3, pp. 187-215, 2007

Authors: Chang, Chin-Chen | Tai, Wei-Liang | Lin, Chia-Chen

Article Type: Research Article

Abstract: Data hiding is popularly employed in protecting the copyright, secret information and communication secretly with the convenience of network communication. In order to reduce the amount the transmitted data via network, VQ (vector quantization) is applied to compressing the transmitted data. Since VQ is a low-bit-rate compression scheme, it is difficult to find large redundant hiding space and to get stego-images with high quality for hiding data in VQ-based compressed images. A hiding method for VQ-based …compressed images is proposed in this paper according to the Hamming distance between the index values of codewords. Our method makes hiding data more effective and provides stego-images with higher quality than other conventional methods. Experimental results demonstrate the effectiveness and the feasibility of our method. Show more

Keywords: Data hiding, vector quantization (VQ), hamming distance

Citation: Fundamenta Informaticae, vol. 77, no. 3, pp. 217-228, 2007

Authors: Li, Yancang | Li, Wanqing

Article Type: Research Article

Abstract: In order to solve the premature convergence problem of the basic Ant Colony Optimization algorithm, a promising modification based on the information entropy is proposed. The main idea is to evaluate stability of the current space of represented solutions using information entropy, which is then applied to turning of the algorithm's parameters. The path selection and evolutional strategy are controlled by the information entropy self-adaptively. Simulation study and performance comparison with other Ant …Colony Optimization algorithms and other meta-heuristics on Traveling Salesman Problem show that the improved algorithm, with high efficiency and robustness, appears self -adaptive and can converge at the global optimum with a high probability. The work proposes a more general approach to evolutionary-adaptive algorithms related to the population's entropy and has significance in theory and practice for solving the combinatorial optimization problems. Show more

Keywords: Ant Colony Optimization, modification, information entropy, self-adaptive, Traveling Salesman Problem

Citation: Fundamenta Informaticae, vol. 77, no. 3, pp. 229-242, 2007

Authors: Pechenizkiy, Mykola | Tsymbal, Alexey | Puuronen, Seppo | Patterson, David

Article Type: Research Article

Abstract: Recent research has shown the integration of multiple classifiers to be one of the most important directions in machine learning and data mining. In this paper, we present an algorithm for the dynamic integration of classifiers in the space of extracted features (FEDIC). It is based on the technique of dynamic integration, in which local accuracy estimates are calculated for each base classifier of an ensemble, in the neighborhood of a new instance to be processed. …Generally, the whole space of original features is used to find the neighborhood of a new instance for local accuracy estimates in dynamic integration. However, when dynamic integration takes place in high dimensions the search for the neighborhood of a new instance is problematic, since the majority of space is empty and neighbors can in fact be located far from each other. Furthermore, when noisy or irrelevant features are present it is likely that also irrelevant neighbors will be associated with a test instance. In this paper, we propose to use feature extraction in order to cope with the curse of dimensionality in the dynamic integration of classifiers. We consider classical principal component analysis and two eigenvector-based class-conditional feature extraction methods that take into account class information. Experimental results show that, on some data sets, the use of FEDIC leads to significantly higher ensemble accuracies than the use of plain dynamic integration in the space of original features. Show more

Keywords: feature extraction, dynamic integration of classifiers

Citation: Fundamenta Informaticae, vol. 77, no. 3, pp. 243-275, 2007

Authors: Porwik, Piotr

Article Type: Research Article

Abstract: This paper presents the spectralmethod of recognition of an incompletely defined Boolean function. The main goal of analysis is fast estimation whether a given single output function can be extended to affine form. Furthermore, a simple extension algorithm is proposed for functions, for which the affine form is reachable. The algorithm is compared with other methods. Theoretical and experimental results demonstrate the efficiency of the presented approach.

Keywords: Walsh coefficients, coefficients distribution, incompletely defined Boolean function, affine function

Citation: Fundamenta Informaticae, vol. 77, no. 3, pp. 277-291, 2007