Fundamenta Informaticae - Volume 73, issue 3

Authors: Analyti, Anastasia | Pachoulakis, Ioannis

Article Type: Research Article

Abstract: The Compound Term Composition Algebra (CTCA) is an algebra with four algebraic operators, which can be used to generate the valid (meaningful) compound terms of a given faceted taxonomy, in an efficient and flexible manner. The positive operations allow the derivation of valid compound terms through the declaration of a small set of valid compound terms. The negative operations allow the derivation of valid compound terms through the declaration of a small set of invalid compound …terms. In this paper, we show how CTCA can be represented in logic programming with negation-as-failure, according to both Clark's and well-founded semantics. Indeed, the SLDNF-resolution can be used for checking compound term validity and well-formedness of an algebraic expression in polynomial time w.r.t. the size of the expression and the number of terms in the taxonomy. This result makes our logic programming representation a competitive alternative to imperative algorithms. Embedding of our logic programming representation to the programming environment of a web portal for a computer sales company is demonstrated. Show more

Keywords: Faceted Taxonomies, Logic Programming, Computational Complexity, Applications

Citation: Fundamenta Informaticae, vol. 73, no. 3, pp. 321-360, 2006

Authors: Dinu, Liviu P. | Sgarro, Andrea

Article Type: Research Article

Abstract: We exhibit a low-complexity but non-trivial distance between strings to be used in biology. The experimental results we provide were obtained on a standard laptop and, even if preliminary, are quite encouraging.

Keywords: metrics, rank distance, DNA sequencing, bioinformatics, phylogeny

Citation: Fundamenta Informaticae, vol. 73, no. 3, pp. 361-372, 2006

Authors: Hu, Yu-Chen

Article Type: Research Article

Abstract: A low-complexity grayscale image embedding scheme that can embed multiple secret images is proposed in this paper. In this scheme, different users can extract different secret images according to the secret keys they hold. To reduce the storage cost of the secret images, each of the secret images is first compressed using an improved version of the moment preserving block truncation coding scheme. The compressed message of each secret image is then encrypted by the DES …cryptography system with different secret key and then embedded into the host image using the modulus least-significant-bit substitution technique. According to the experimental results, it is shown that the proposed scheme consumes a little computational cost. Besides, different users can extract different number of secret images. In other words, the proposed scheme indeed provides a good approach for the hiding of grayscale images with access control. Show more

Keywords: image hiding, block truncation coding, DES

Citation: Fundamenta Informaticae, vol. 73, no. 3, pp. 373-387, 2006

Authors: Liu, Weiru | Qi, Guilin | Bell, David A.

Article Type: Research Article

Abstract: In this paper, we propose an adaptive algorithm for merging n (⩾2) prioritized knowledge bases which takes into account the degrees of conflict and agreement among these knowledge bases. The algorithm first selects largely partially maximal consistent subsets (LPMCS) of sources by assessing how (partially) consistent the information in the subset is. Then within each of these created subsets, a maximal consistent subset is further selected and knowledge bases in it are merged with a suitable …conjunctive operator based on the degree of agreement among them. This result is then merged with the remaining knowledge bases in the corresponding LPMCS in the second step through the relaxation of the minimum operator. Finally, the knowledge bases obtained from the second step are merged by a maximum operator. In comparison with other merging methods, our approach is more context dependent and is especially useful when most sources of information are in conflict. Show more

Keywords: Possibilistic logic, prioritized knowledge bases, belief merging, context dependent merging

Citation: Fundamenta Informaticae, vol. 73, no. 3, pp. 389-407, 2006

Authors: Pinna, G. Michele

Article Type: Research Article

Abstract: In recent years the consideration that events in evolutions of concurrent systems can happen with different histories has received ground. In particular the possibility that part of the history can be abstracted away or identified, like in the collective tokens philosophy for Petri Nets, has gained the stage. The various brands of event structures considered in literature are tailored to a fixed interpretation with respect to the history of an event. We investigate the adequateness of …event structures with a disabling/enabling relation, to settle a common ground for the history dependent and history independent interpretations, and we establish a relationship between event automata and these notions of event structures. Show more

Keywords: Event Structures, Event Automata, Models for Concurrency

Citation: Fundamenta Informaticae, vol. 73, no. 3, pp. 409-430, 2006