Fundamenta Informaticae - Volume 70, issue 3

Authors: Chang, Chin-Chen | Chuang, Jun-Chou | Hu, Yu-Chen

Article Type: Research Article

Abstract: In this paper, we present a spatial domain Image hiding scheme that embeds secret data in a gray-level image. Our scheme is inspired from Wu and Tsai's scheme that embeds secret bits in the difference values of consecutive pixels. To improve the hiding capacity of their scheme, the overlapping concept is proposed to produce more difference values from the cover image in this paper. Experimental results show that our scheme provides an average hiding capacity gain …of 84.16% over Wu and Tsai's scheme while maintaining satisfactory image quality. Show more

Keywords: data hiding, steganography, image hiding, LSB, DES, RSA

Citation: Fundamenta Informaticae, vol. 70, no. 3, pp. 171-184, 2006

Authors: Chang, Chin-Chen | Lin, Chih-Yang | Chou, Henry

Article Type: Research Article

Abstract: Hashing schemes are a common technique to improve the performance in mining not only association rules but also sequential patterns or traversal patters. However, the collision problem in hash schemes may result in severe performance degradation. In this paper, we propose perfect hashing schemes for mining traversal patterns to avoid collisions in the hash table. The main idea is to transform each large itemsets into one large 2-itemset by employing a delicate encoding scheme. Then perfect …hash schemes designed only for itemsets of length two, rather than varied lengths, are applied. The experimental results show that our method is more than twice as faster than FS algorithm. The results also show our method is scalable to database sizes. One variant of our perfect hash scheme, called partial hash, is proposed to cope with the enormous memory space required by typical perfect hash functions. We also give a comparison of the performances of different perfect hash variants and investigate their properties. Show more

Keywords: data mining, traversal patterns, perfect hashing, performance analysis

Citation: Fundamenta Informaticae, vol. 70, no. 3, pp. 185-202, 2006

Authors: Devillers, Raymond | Klaudel, Hanna | Koutny, Maciej

Article Type: Research Article

Abstract: In this paper we propose a translation into high level Petri nets of the terms of a finite fragment of the π-calculus. Our construction renders in a compositional way the control flow aspects present in π-calculus process expressions, by adapting the existing graph-theoretic net composition operators. Those aspects which are related to term rewriting, as well as name binding, are handled through special inscriptions of places, transitions and arcs, together with a suitable choice of the …initial marking. Show more

Citation: Fundamenta Informaticae, vol. 70, no. 3, pp. 203-226, 2006

Authors: Gasquet, Olivier

Article Type: Research Article

Abstract: In this paper we prove that adding a confluence axiom to a modal logic which behaves rather well from the viewpoint of complexity of the satisfaction problem, drastically increases its complexity and blows it up from PSPACE-completeness to NEXPTIME-completeness. More precisely, we investigate here both monomodal K + confluence and bimodal K with confluence between the two modalities.

Keywords: Modal Logics, Tableaux, Confluence, Complexity, Satisfaction problem, Tiling problem, NEXPTIME-completeness

Citation: Fundamenta Informaticae, vol. 70, no. 3, pp. 227-250, 2006

Authors: Hu, Yu-Chen | Chang, Chin-Chen

Article Type: Research Article

Abstract: In this paper, an improved tree-structured codebook search algorithm is proposed. It is called the two-level codebook search algorithm (TLCS). The goal of this method is to reduce the computation cost of the multi-path-searching algorithm for TSVQ. It speeds up the codebook search by searching only a two-level codebook tree instead of the whole TSVQ codebook tree. According to the experimental results, a significant time reduction can be achieved with this method, compared to the multi-path-searching …algorithm. In other words, our TLCS outperforms the multi-path-searching algorithm. Show more

Citation: Fundamenta Informaticae, vol. 70, no. 3, pp. 251-260, 2006

Authors: Jaworski, Wojciech

Article Type: Research Article

Abstract: In this paper we derive the bounds for Validation (known also as Hold-Out Estimate and Train-and-Test Method). We present the best possible bound in the case of 0–1 valued loss function. We also provide the tables where the least sample size is calculated that is necessary for obtaining the bound for a given estimation rate and reliability of estimation. For an arbitrary bounded loss function we present the optimal bound approximation with any given accuracy.

Keywords: computational learning theory, model assessment, hold-out estimate, train-and-test, validation, Bernoulli sums

Citation: Fundamenta Informaticae, vol. 70, no. 3, pp. 261-275, 2006

Authors: Sali, Attila | Schewe, Klaus-Dieter

Article Type: Research Article

Abstract: We investigate functional dependencies (FDs) in the presence of several constructors for complex values. These constructors are the tuple constructor, list-, set- and multiset-constructors, an optionality constructor, and a disjoint union constructor. The disjoint union constructor implies restructuring rules, which complicate the theory. In particular, they do not permit a straightforward axiomatisation of the class of all FDs without a detour via weak functional dependencies (wFDs), i.e. disjunctions of functional dependencies, and …even the axiomatisation of wFDs is not yet completely solved. Therefore, we look at the restricted class of counter-free functional dependencies (cfFDs). That is, we ignore subattributes that only refer to counting the number of elements in sets or multisets or distinguish only between empty or non-empty sets. We present a finite axiomatisation for the class of cfFDs. Furthermore, we study keys ignoring again the counting subattributes. We show that such keys are equivalent with certain ideals called HL-ideals. Based on that we introduce an ordering between key sets, and investigate systems of minimal keys. We give a sufficient condition for a Sperner family of HL-ideals being a system of minimal keys, and determine lower and upper bounds for the size of the smallest Armstrong-instance. Show more

Keywords: functional dependencies, keys, type constructors, axiomatisation, Sperner families

Citation: Fundamenta Informaticae, vol. 70, no. 3, pp. 277-301, 2006