Fundamenta Informaticae - Volume 78, issue 2

Authors: Bolikowski, Łukasz | Gambin, Anna

Article Type: Research Article

Abstract: In this paper we propose two new metrics defined on the space of phylogenetic trees. The problem of determining how distant two trees are from each other is crucial because many various methods exist for reconstructing phylogenetic trees from molecular data. These techniques (in fact often heuristics) applied to the same data set result in significantly different trees. We investigate the basic properties of new metrics and present efficient algorithms approximating the distance between …two trees for partition metric. Computational experiments, which has been performed for large family of trees justify the applicability of our algorithms. The interesting application of our framework is the identification of the ancestral paralog position in the paralog families. We propose to select the set of genes (exemplars) that minimize the partition metric distance between gene tree and species tree. Show more

Citation: Fundamenta Informaticae, vol. 78, no. 2, pp. 199-216, 2007

Authors: Breysse, Olivia | De Glas, Michel

Article Type: Research Article

Abstract: Mereotopology is a class of formal theories devoted to the analysis of spatiotemporal entities and their interactions. It has produced important advances in the analysis of natural language, naive geography and computer vision, illustrating a broad range of applications. However, it has been shown that the modelling of interactions between spatiotemporal entities with mereotopology can lead to unsolvable problems, including disconnectedness of the representation space as well as a mixup of the relationships of contact and …overlap. The origin of these problems, which fundamentally limit the usefulness of mereotopology, has not been fully identified. In this paper, we first formally demonstrate that these problems originate from the incompatibility of the concepts of boundary, continuity and contact within the framework of mereotopology, as suggested by previous studies. Secondly, we prove that this incompatibility stems from the formalization of these concepts through topology. We show that a solution can be found by substituting for topology an alternative theory, known as locology, which provides new mathematical tools for the modelling of spatiotemporal entities. Show more

Keywords: Boundary, Contact, Continuity, Mereotopology, Locology

Citation: Fundamenta Informaticae, vol. 78, no. 2, pp. 217-238, 2007

Authors: Hu, Yu-Chen

Article Type: Research Article

Abstract: A predictive image compression scheme that combines the advantages of vector quantization and moment preserving block truncation coding is introduced in this paper. To exploit the similarities among neighboring image blocks, the block prediction technique is employed in this scheme. If a similar compressed image block can be found in the neighborhood of current processing block, it is taken to encode this block. Otherwise, this image block is encoded either by vector quantization or moment preserving …block truncation coding. A bit-rate reduced version of the proposed scheme is also introduced. According to the experimental results, it is shown that the proposed scheme provides better image quality at a low bitrate than these comparative schemes. Show more

Keywords: image compression, vector quantization, block truncation coding, bit map coding

Citation: Fundamenta Informaticae, vol. 78, no. 2, pp. 239-255, 2007

Authors: Hu, Yu-Chen | Lin, Chia-Chen | Chi, Kang-Liang

Article Type: Research Article

Abstract: This paper presents a new image compression scheme based on vector quantization (VQ) that exploits the inter-block and intra-block correlations in grayscale images. The similar block prediction technique is designed to encode the image blocks by their similar neighboring encoded blocks. Besides, two codebooks are used in the proposed scheme to exploit the intra-block correlation within each image block. Experimental results show that the proposed scheme not only provides good image qualities but also cuts down …the required bit rates. Show more

Citation: Fundamenta Informaticae, vol. 78, no. 2, pp. 257-270, 2007

Authors: Huynh, Van Nam | Nakamori, Yoshiteru | Murai, Tetsuya

Article Type: Research Article

Abstract: It is well known that algebraization has been successfully applied to classical and nonclassical logics (Rasiowa and Sikorski, 1968). Following this direction, an ordered-based approach to the problem of finding out a tool to describe algebraic semantics of Zadeh's fuzzy logic has been introduced and developed by Nguyen Cat-Ho and colleagues during the last decades. In this line of research, RH algebra has been introduced in [20] as a unified algebraic approach to the natural structure …of linguistic domains of linguistic variables. It was shown that every RH algebra of a linguistic variable with a chain of the primary terms is a distributive lattice. In this paper we will examine algebraic structures of RH algebras corresponding to linguistic domains having exactly two distinct primary terms, one being an antonym of the other, called symmetrical RH algebras. Computational results for the relatively pseudo-complement operation in these algebras will be given. Show more

Keywords: Linguistic reasoning, fuzzy logic, linguistic variable, hedge algebra, RH-algebra, distributive lattice

Citation: Fundamenta Informaticae, vol. 78, no. 2, pp. 271-294, 2007

Authors: Palka, Ewa

Article Type: Research Article

Abstract: We present an infinitary logic ACT_ω in the form of a Gentzen-style sequent system, which is equivalent to the equational theory of *-continuous action lattices [9]. We prove the cut-elimination theorem for ACT_ω and, as a consequence, a theorem on the elimination of negative occurrences of *. This shows that ACT_ω is Π^0_1 , whence, by a result of Buszkowski [1], it is Π^0_1 complete.

Keywords: Kleene algebra, action algebra, action lattice, cut-elimination, complexity

Citation: Fundamenta Informaticae, vol. 78, no. 2, pp. 295-309, 2007