Fundamenta Informaticae - Volume 96, issue 1-2

Authors: Bandyopadhyay, Sanghamitra | Bhattacharyya, Malay

Article Type: Research Article

Abstract: An important problem of knowledge discovery that has recently evolved in various reallife networks is identifying the largest set of vertices that are functionally associated. The topology of many real-life networks shows scale-freeness, where the vertices of the underlying graph follow a power-law degree distribution. Moreover, the graphs corresponding to most of the real-life networks are weighted in nature. In this article, the problem of finding the largest group or association of vertices that are dense …(denoted as dense vertexlet) in a weighted scale-free graph is addressed. Density quantifies the degree of similarity within a group of vertices in a graph. The density of a vertexlet is defined in a novel way that ensures significant participation of all the vertices within the vertexlet. It is established that the problem is NP-complete in nature. An upper bound on the order of the largest dense vertexlet of a weighted graph, with respect to certain density threshold value, is also derived. Finally, an O(n^2 log n) (n denotes the number of vertices in the graph) heuristic graph mining algorithm that produces an approximate solution for the problem is presented. Show more

Keywords: Graphs and networks, scale-free, mining methods and algorithms, knowledge discovery, bioinformatics

DOI: 10.3233/FI-2009-164

Citation: Fundamenta Informaticae, vol. 96, no. 1-2, pp. 1-25, 2009

Authors: Bergstra, Jan A. | Middelburg, Cornelis A.

Article Type: Research Article

Abstract: We study sequential programs that are instruction sequences with dynamically instantiated instructions. We define the meaning of such programs in two different ways. In either case, we give a translation by which each program with dynamically instantiated instructions is turned into a program without them that exhibits on execution the same behaviour by interaction with some service. The complexity of the translations differ considerably, whereas the services concerned are equally simple. However, the service concerned …in the case of the simpler translation is far more powerful than the service concerned in the other case. Show more

Keywords: instruction sequence, dynamically instantiated instruction, projection semantics, program algebra, thread algebra, action transforming use mechanism

DOI: 10.3233/FI-2009-165

Citation: Fundamenta Informaticae, vol. 96, no. 1-2, pp. 27-48, 2009

Authors: Chan, Chi-Shiang

Article Type: Research Article

Abstract: The proposedmethod in this paper is based on the LSB matching function ofMielikainen for Steganography. However, there is a significant change with respect to Mielikainen's method in the use of the LSB matching function to compute secret bits. Melikainen extracts secret bits in pixel pairs: the first one is the LSB of the first pixel in a pixel pair and the other is computed by a LSB matching function applied to both pixels. The proposed method …does not make any partition, but makes the sequential image processing: the current secret bit is always computed by a LSB matching function where the LSB matching function is modified using only an XOR operation. To make the data extraction compatible with data embedding, the proposed method modifies sparse pixels by adding/subtracting their value to/from one. In the experimental results, the values of embedding efficiency increase while the involved bits increase. Taking test images in the experiments, the numbers of modified pixels in the proposed method are always lower than those in Mielikainen's method. Show more

Keywords: Information hiding, LSB matching, LSB matching revisited

DOI: 10.3233/FI-2009-166

Citation: Fundamenta Informaticae, vol. 96, no. 1-2, pp. 49-59, 2009

Authors: Chen, Tzung-Her | Tsao, Kai-Hsiang | Yang, Yan-Ting

Article Type: Research Article

Abstract: The visual secret sharing (VSS) approach by random grids (RG-based VSS) has drawn people's attention "again" recently. Nevertheless, the current RG-based VSS approaches suffer from the problem of meaningless share images (cipher-grids) so that it is not user-friendly to manage noise-like share images. This paper presents a novel color RG-based VSS scheme aiming at providing the friendly color cipher-grids with all the advantages of traditional VSS schemes. To our best knowledge, this …paper is the first effort to develop the friendly technique. The experimental results show that the scheme does work. Show more

Keywords: Random Grid, Visual Secret Sharing, Visual Cryptography, Friendly, Meaningful

DOI: 10.3233/FI-2009-167

Citation: Fundamenta Informaticae, vol. 96, no. 1-2, pp. 61-70, 2009

Authors: Dassow, Jürgen | Martín, Gema M. | Vico, Francisco J.

Article Type: Research Article

Abstract: A cyclic unary regular language is a regular language over a unary alphabet that is represented by a cyclic automaton. We propose a similarity measure for cyclic unary regular languages by modifying the Jaccard similarity coefficient and the Sørensen coefficient to measure the level of overlap between such languages. This measure computes the proportion of strings that are shared by two or more cyclic unary regular languages and is an upper bound of the Jaccard coefficient …and the Sørensen coefficient. By using such similarity measure, we define a dissimilarity measure for cyclic unary regular languages that is a semimetric distance. Moreover, it can be used for the non-cyclic case. Show more

Keywords: Similarity measure, cyclic unary regular language, Jaccard coefficient, Sørensen coef- ficient

DOI: 10.3233/FI-2009-168

Citation: Fundamenta Informaticae, vol. 96, no. 1-2, pp. 71-88, 2009

Authors: Janodet, ean-Christophe | Sebban, Marc | Suchier, Henri-Maxime

Article Type: Research Article

Abstract: We focus on the adaptation of boosting to representation spaces composed of different subsets of features. Rather than imposing a single weak learner to handle data that could come from different sources (e.g., images and texts and sounds), we suggest the decomposition of the learning task into several dependent sub-problems of boosting, treated by different weak learners, that will optimally collaborate during the weight update stage. To achieve this task, we introduce a new weighting scheme …for which we provide theoretical results. Experiments are carried out and show that ourmethod works significantly better than any combination of independent boosting procedures. Show more

Keywords: Machine learning, boosting, heterogeneous features, subsets of features, convergence proofs

DOI: 10.3233/FI-2009-169

Citation: Fundamenta Informaticae, vol. 96, no. 1-2, pp. 89-109, 2009

Authors: Koutras, Costas D. | Zikos, Yorgos

Article Type: Research Article

Abstract: An important question in modal nonmonotonic logics concerns the limits of propositional definability for logics of the McDermott-Doyle family. Inspired by this technical question we define a variant of autoepistemic logic which provably corresponds to the logic of the McDermott-Doyle family that is based on themodal axiom p5: ◊φ⊃ (¬□φ⊃□¬□φ). This axiomis a naturalweakening of classical negative introspection restricting its scope to possible facts. It closely resembles the axiom w5: φ⊃ (¬□φ⊃□¬□φ) …which restricts the effect of negative introspection to true facts. We examine p5 in the context of classical possible-worlds Kripke models, providing results for correspondence, completeness and the finite model property. We also identify the corresponding condition for p5 in the context of neighbourhood semantics. Although rather natural epistemically, this axiom has not been investigated in classical modal epistemic reasoning, probably because its addition to S4 gives the well-known strong modal system S5. Show more

DOI: 10.3233/FI-2009-170

Citation: Fundamenta Informaticae, vol. 96, no. 1-2, pp. 111-125, 2009

Authors: Lanotte, Ruggero | Beauquier, Danièle

Article Type: Research Article

Abstract: In this paper we extend the predicate logic introduced by Beauquier et al. in order to deal with Markov decision processes. We prove that with respect to qualitative probabilistic properties, model checking is decidable for this logic applied to Markov decision processes. Furthermore we apply our logic to probabilistic timed transition systems using predicates on clocks. We prove that results on Markov decision processes hold also for probabilistic timed transition systems. The interest of this …logic lies in particular on the fact that some important properties are expressible in this logic but not expressible in pCTL. Show more

Keywords: Markov Decision Processes, Probabilistic Timed Transition Systems, Model Checking, Predicate logic of Probabilities

DOI: 10.3233/FI-2009-171

Citation: Fundamenta Informaticae, vol. 96, no. 1-2, pp. 127-151, 2009

Authors: Rital, Soufiane

Article Type: Research Article

Abstract: This paper presents a novel approach to image segmentation based on hypergraph cut techniques. Natural images contain more components: Edge, homogeneous region, noise. So, to facilitate the natural image analysis, we introduce an Image Neighborhood Hypergraph representation (INH). This representation extracts all features and their consistencies in the image data and its mode of use is close to the perceptual grouping. Then, we formulate an image segmentation problem as a hypergraph partitioning problem and we use …the recent k-way hypergraph techniques to find the partitions of the image into regions of coherent brightness/color. Experimental results of image segmentation on a wide range of images from Berkeley Database show that the proposed method provides a significant performance improvement compared with the stat-of-the-art graph partitioning strategy based on Normalized Cut (Ncut) criteria. Show more

Keywords: hypergraph partitioning algorithms, image segmentation, image neighborhood hypergraph representation (INH), normalized cuts

DOI: 10.3233/FI-2009-172

Citation: Fundamenta Informaticae, vol. 96, no. 1-2, pp. 153-179, 2009

Authors: Rudnicki, Witold R. | Jankowski, Aleksander | Modzelewski, Aleksander | Piotrowski, Aleksander | Zadrożny, Adam

Article Type: Research Article

Abstract: Algorithms for estimating similarity between two macromolecular sequences are of profound importance for molecular biology. The standard methods utilize so-called primary structure, that is a string of characters denoting the sequence of monomers in hetero-polymer. These methods find the substrings of maximal similarity, as defined by the so-called similarity matrix, for a pair of two molecules. The problem is solved either by the exact dynamic programming method, or by approximate heuristic methods. The …approximate algorithms are almost two orders of magnitude faster in comparison with the standard version of the exact Smith-Waterman algorithm, when executed on the same hardware, hence the exact algorithm is relatively rarely used. Recently a very efficient implementation of Smith- Waterman algorithm utilizing SIMD extensions to the standard instruction set reduced the speed advantage of heuristic algorithms to factor of three. Here we present an improved implementation of the Smith-Waterman algorithm on the Cell processor. Implementation presented here achieves execution speed of approximately 9 GCUPS. The performance is independent on the scoring system. It is 4 to 10 times faster than best Smith-Waterman implementation running on a PC and 1.5 to 3 times faster than the same implementation running on Sony PlayStation 3. It is also 5 times faster than the recent implementation of the Smith- Waterman utilizing Nvidia GPU. Our implementation running on Sony PlayStation 3 has performance which is directly comparable with that of BLAST running on PC, being up to 4 times faster in the best case and no more than two times slower in the worst case. This performance level opens possibility for using the exact Smith-Waterman algorithm in applications, where currently approximate algorithms are used. Show more

Keywords: bioinformatics, protein sequence alignment, Cell processor

DOI: 10.3233/FI-2009-173

Citation: Fundamenta Informaticae, vol. 96, no. 1-2, pp. 181-194, 2009