Fundamenta Informaticae - Volume 71, issue 4

Authors: Chaitin, Gregory

Article Type: Research Article

Abstract: We show that unlike the general case of the relationship between algorithmic probability and program-size for enumerating sets, in the case of the graphs of total functions these two quantities are closely related.

Citation: Fundamenta Informaticae, vol. 71, no. 4, pp. 367-370, 2006

Authors: Christiansen, Henning | Martinenghi, Davide

Article Type: Research Article

Abstract: Without proper simplification techniques, database integrity checking can be prohibitively time consuming. Several methods have been developed for producing simplified incremental checks for each update but none until now of sufficient quality and generality for providing a true practical impact, and the present paper is an attempt to fill this gap. On the theoretical side, a general characterization is introduced of the problem of simplification of integrity constraints and a natural definition is given of …what it means for a simplification procedure to be ideal. We prove that ideality of simplification is strictly related to query containment; in fact, an ideal simplification pro-cedure can only exist in database languages for which query containment is decidable. However, simplifications that do not qualify as ideal may also be relevant for practical purposes. We present a concrete approach based on transformation operators that apply to integrity constraints written in a rich DATALOG-like language with negation. The resulting procedure produces, at design-time, simplified constraints for parametric transaction patterns, which can then be instantiated and checked for consistency at run-time. These tests take place before the execution of the update, so that only consistency-preserving updates are eventually given to the database. The extension to more expressive languages and the application of the framework to other contexts, such as data integration and concurrent database systems, are also discussed. Our experiments show that the simplifications obtained with our method may give rise to much better performance than with previous methods and that further improvements are achieved by checking consistency before executing the update. Show more

Keywords: Integrity constraints, simplification, incremental integrity checking

Citation: Fundamenta Informaticae, vol. 71, no. 4, pp. 371-417, 2006

Authors: Kamide, Norihiro

Article Type: Research Article

Abstract: An extended first-order predicate sequent calculus PLK with two kinds of negation is introduced as a basis of a new resolution calculus PRC (paraconsistent resolution calculus) for handling the property of paraconsistency. Herbrand theorem, completeness theorem (with respect to a classical-like semantics) and cut-elimination theorem are proved for PLK. The correspondence between PLK and PRC is shown by using a faithful embedding of PLK into the sequent calculus LK for classical logic.

Keywords: Paraconsistent resolution, sequent calculus, Herbrand theorem, completeness, cut-elimination

Citation: Fundamenta Informaticae, vol. 71, no. 4, pp. 419-441, 2006

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

Article Type: Research Article

Abstract: A novel watermarking scheme that is capable of hiding authorization data in a gray-level image is proposed in this letter. The proposed scheme generates a key stream to be the key to connect the authorized image and its watermark. The key stream is extra data rather than data being embedded into the authorized image. Such arrangement can guarantee the integrity of the image. To reduce the complexity in computing the key stream for the authorized gray-level …image, two techniques are employed in the proposed scheme. One is the concept of rehashing, and the other is the vector quantization. The benefits of the proposal are to provide a key stream to prove the gray-level's ownership, and to keep the authorized image in its original state without any modification. Show more

Keywords: Image Hiding, watermark, rehashing concept, vector quantization, key stream

Citation: Fundamenta Informaticae, vol. 71, no. 4, pp. 443-451, 2006

Authors: Kari, L. | Losseva, E. | Konstantinidis, S. | Sosík, P. | Thierrin, G.

Article Type: Research Article

Abstract: The concept of hairpin structures in formal languages is motivated from the biocomputing and bioinformatics fields. Hairpin (-free) DNA structures have numerous applications to DNA computing and molecular genetics in general. A word is called hairpin-free if it cannot be written in the form xuyθ(u)z, with certain additional conditions, for an involution θ (a function θ with the property that θ^2 equals the identity function). A particular involution, the so-called Watson-Crick …involution, can characterize binding of two DNA strands. We study algebraic and decision properties, finiteness and descriptional complexity of hairpin (-free) languages. We show an existence of polynomial-time algorithms deciding hairpin-freeness of regular and context-free sets. Two related DNA secondary structures are considered, taking into the account imperfect bonds (bulges, mismatches) and multiple hairpins. Finally, effective methods for design of long hairpin-free DNA words are given. Show more

Keywords: DNA computing, DNA hairpin, involution, formal language

Citation: Fundamenta Informaticae, vol. 71, no. 4, pp. 453-475, 2006

Authors: Winter, Michael

Article Type: Research Article

Abstract: Subtyping is a basic concept in object-oriented languages. It supports subsumption but, unfortunately, it does not support inheritance of binary methods, i.e., methods taking another argument of type Self? – the same type as the object itself. For this reason, a relation, called matching, on recursive object types has been proposed. This relation does not support subsumption but it allows to inherit binary methods. Two different definitions of matching, called F-bounded and higher-order subtyping, have been …proposed and discussed. It was shown that the higher-order interpretation has better theoretical properties, i.e., it leads to a reflexive and transitive matching relation. In this paper we concentrate on two problems in languages with self types and matching based on the higher-order interpretation. We show that the flexibility of self types may not allow the programmer to define certain classes and/or methods which are based on constant values. Furthermore, the higher-order interpretation, especially in the context of bounded quantification, is too restrictive. We argue that a language should be based on both versions of matching and a notion of a type This distinguished from the type Self. Show more

Citation: Fundamenta Informaticae, vol. 71, no. 4, pp. 477-491, 2006

Authors: Zhong, Sheng

Article Type: Research Article

Abstract: Traditionally, due to efficiency considerations, when encrypting long messages using an asymmtric cryptosystem, one needs to use a symmetric cryptosystem in addition. To eliminate this requirement, Hwang, Chang, and Hwang introduced an asymmetric cryptosystem for encrypting long messages. However, they did not give any formal proof of the security of this cryptosystem. In this paper, we propose an improved asymmetric cryptosystem for encrypting long messages, which is both efficient and secure. In the aspect of …efficiency, our cryptosystem is about twice as fast as the Hwang-Chang-Hwang cryptosystem. In the aspect of security, besides providing an informal analysis, we rigorously show that computing any part of the plaintext message encrypted using our cryptosystem is as hard as breaking the ElGamal cryptosystem, even if all other parts of the message are already known to the adversary. Show more

Keywords: Cryptosystem, data security, encryption, public key

Citation: Fundamenta Informaticae, vol. 71, no. 4, pp. 493-497, 2006