Fundamenta Informaticae - Volume 101, issue 3

Authors: Aratsu, Taku | Hirata, Kouichi | Kuboyama, Tetsuji

Article Type: Research Article

Abstract: This article proposes an approximation of the tree edit distance through the string edit distance for binary tree codes, instead of for Euler strings introduced by Akutsu (2006). Here, a binary tree code is a string obtained by traversing a binary tree representation with two kinds of dummy nodes of a tree in preorder. Then, we show that σ/2 ≤ τ ≤ (h + 1)σ + h, where τ is the tree edit distance between trees, and σ is the string edit distance between their binary tree codes and h is the minimum height of the trees.

Keywords: tree edit distance, string edit distance, binary tree code, binary tree representation

DOI: 10.3233/FI-2010-282

Citation: Fundamenta Informaticae, vol. 101, no. 3, pp. 157-171, 2010

Authors: Crochemore, Maxime | Kubica, Marcin | Waleń, Tomasz | Iliopoulos, Costas S. | Rahman, M. Sohel

Article Type: Research Article

Abstract: In this paper, we study the pattern matching problem in given intervals. Depending on whether the intervals are given a priori for pre-processing, or during the query along with the pattern or, even in both the cases, we develop efficient solutions for different variants of this problem. In particular, we present efficient indexing schemes for each of the above variants of the problem.

Keywords: algorithms, data structures, pattern matching, strings

DOI: 10.3233/FI-2010-283

Citation: Fundamenta Informaticae, vol. 101, no. 3, pp. 173-186, 2010

Authors: Hońko, Piotr

Article Type: Research Article

Abstract: In this paper, we introduce a method for measuring similarity of objects of a relational database (relational objects, in short). We also propose and investigate an algorithm SC for classification of relational objects. The task of classification is carried out based on similarity of the objects to predefined classes. An object to be classified is assigned to the class to which it is most similar. A similarity of an object to a class is understood as its similarity to a class representative. Several methods for computing the class representative are proposed. We test the algorithm on real and artificial databases. …We compare results obtained by the algorithm with those obtained by other algorithms known from the literature. We also present our approach in the context of granular computing. Show more

Keywords: multi-relational data mining, classification, similarity measures, granular computing

DOI: 10.3233/FI-2010-284

Citation: Fundamenta Informaticae, vol. 101, no. 3, pp. 187-213, 2010

Authors: Kari, Lila | Seki, Shinnosuke

Article Type: Research Article

Abstract: Considering two DNA molecules which are Watson-Crick (WK) complementary to each other “equivalent” with respect to the information they encode enables us to extend the classical notions of repetition, period, and power. WK-complementarity has been modelled mathematically by an antimorphic involution θ, i.e., a function θ such that θ(xy) = θ(y)θ(x) for any x, y ∞ Σ*, and θ2 is the identity. The WK-complementarity being thus modelled, any word which is a repetition of u and θ(u) such as uu, uθ(u)u, and uθ(u)θ(u)θ(u) can be regarded repetitive in this sense, and hence, called a θ-power of u. Taking the …notion of θ-power into account, the Fine and Wilf’s theorem was extended as “given an antimorphic involution θ and words u, v, if a θ-power of u and a θ-power of v have a common prefix of length at least b(|u|, |v|) = 2|u| + |v| – gcd(|u|, |v|), then u and v are θ-powers of a same word.” In this paper, we obtain an improved bound b′(|u|, |v|) = b(|u|, |v|) – [gcd(|u|, |v|)/2]. Then we show all the cases when this bound is optimal by providing all the pairs of words (u, v) such that they are not θ-powers of a same word, but one can construct a θ-power of u and a θ-power of v whose maximal common prefix is of length equal to b′(|u|, |v|) − 1. Furthermore, we characterize such words in terms of Sturmian words. Show more

Keywords: (extended) Fine and Wilf’s theorem, pseudo-primitivity, antimorphic involution, optimal bound, Sturmian word

DOI: 10.3233/FI-2010-285

Citation: Fundamenta Informaticae, vol. 101, no. 3, pp. 215-236, 2010

Authors: Liu, Guohua | You, Jia-Huai

Article Type: Research Article

Abstract: Level mapping and loop formulas are two different means to justify and characterize answer sets for normal logic programs. Both of them specify conditions under which a supported model is an answer set. Though serving a similar purpose, in the past the two have been studied largely in isolation with each other. In this paper, we study level mapping and loop formulas for weight constraint and aggregate (logic) programs. We show that, for these classes of programs, loop formulas can be devised from level mapping characterizations. First, we formulate a level mapping characterization of stable models and show that it …leads to a new formulation of loop formulas for arbitrary weight constraint programs, without using any new atoms. This extends a previous result on loop formulas for weight constraint programs, where weight constraints contain only positive literals. Second, since aggregate programs are closely related to weight constraint programs, we further use level mapping to characterize the underlying answer set semantics based on which we formulate loop formulas for aggregate programs. The main result is that for aggregate programs not involving the inequality comparison operator, the dependency graphs can be built in polynomial time. This compares to the previously known exponential time method. Show more

Keywords: Logic programs, answer sets, weight constraints, aggregates, loop formulas

DOI: 10.3233/FI-2010-286

Citation: Fundamenta Informaticae, vol. 101, no. 3, pp. 237-255, 2010