Fundamenta Informaticae - Volume 84, issue 1

Article Type: Other

Citation: Fundamenta Informaticae, vol. 84, no. 1, pp. i-ii, 2008

Authors: Amir, Amihood | Levy, Avivit | Reuveni, Liron

Article Type: Research Article

Abstract: Convolutions have proven to be an effective tool in asymptotically efficient pattern matching algorithms. This study attempts to find the type of problems where convolutions are inefficient in practice, and give possible solutions for the complex cases where the convolution method does not seem to aid realistic sized inputs.

Citation: Fundamenta Informaticae, vol. 84, no. 1, pp. 1-15, 2008

Authors: Roh, Kangho | Crochemore, Maxime | Iliopoulos, Costas S. | Park, Kunsoo

Article Type: Research Article

Abstract: In this paper we present external memory algorithms for some string problems. External memory algorithms have been developed in many research areas, as the speed gap between fast internal memory and slow external memory continues to grow. The goal of external memory algorithms is to minimize the number of input/output operations between internal memory and external memory. These years the sizes of strings such as DNA sequences are rapidly increasing. However, external memory algorithms have …been developed for only a few string problems. In this paper we consider five string problems and present external memory algorithms for them. They are the problems of finding the maximum suffix, string matching, period finding, Lyndon decomposition, and finding the minimum of a circular string. Every algorithm that we present here runs in a linear number of I/Os in the external memory model with one disk, and they run in an optimal number of disk I/Os in the external memory model with multiple disks. Show more

Keywords: Externalmemory algorithm, maximum suffix, string matching, period finding, Lyndon decomposition, minimum of a circular string

Citation: Fundamenta Informaticae, vol. 84, no. 1, pp. 17-32, 2008

Authors: Zhang, Hui | Guo, Qing | Iliopoulos, Costas S.

Article Type: Research Article

Abstract: We introduce the notion of λ-regularities in strings that consist of λ-covers and λ-seeds, and study three λ-regularities problems – the λ-cover problem, the general λ-cover problem and the λ-seed problem in this paper. λ-regularities can be viewed as generalized string regularities in the sense that a set of λ repetitive strings rather than a single repeated string are considered. We first present a general algorithm for computing all the λ-combinations of a given …string, since they serve as candidates for both λ-covers and λ-seeds. The running time of this algorithm is O(n^2 ). Relying on this result, we answer the above mentioned three problems all in O(n^2 ) time. Show more

Keywords: the λ-cover problem, the general λ-cover problem, the λ-seed problem, λ-combinations, the Equivalence Class Tree, the Reverses Equivalence Class Tree, String regularities, λ-regularities

Citation: Fundamenta Informaticae, vol. 84, no. 1, pp. 33-49, 2008

Authors: Kelarev, Andrei

Article Type: Research Article

Abstract: This article develops a combinatorial algorithm for a class of codes extending BCH codes and constructed with finite state automata. Our algorithm computes the largest number of errors that the extended codes can correct, and finds a generator for each optimal code in this class of extensions. The question of finding codes with largest possible information rates remains open.

Keywords: finite fields, BCH codes, finite state automata

Citation: Fundamenta Informaticae, vol. 84, no. 1, pp. 51-60, 2008

Authors: Luo, Hongwei | Horadam, Kathy

Article Type: Research Article

Abstract: The main discovery of the paper is the introduction and study of a new U-P complex network model, which aims to describe and analyze many common-featured real-world complex networks. This model employs a new functional form of the network growth rule: a linear combination of preferential and uniform attachment. In particular, the degree distribution of the model is first studied by using the computer simulation method, while the exact solution is also obtained analytically.

Keywords: Complex networks, Scale-free, Small-world, Preferential attachment

Citation: Fundamenta Informaticae, vol. 84, no. 1, pp. 61-79, 2008

Authors: Park, Eunhui | Park, Kunsoo

Article Type: Research Article

Abstract: The Boolean circuit is a simple and realistic model for parallel computation. Chung and Lee considered the problem of finding a maximum matching in a convex bipartite graph, which has two sets of vertices, A and B, such that for any vertex v of A, the neighbors of v in B are contiguous. They gave a Boolean circuit for the problem in O(log^2 n+log n· log log n· log b) depth and O(bn^3 ) size, where n …is the number of vertices in set A of the convex bipartite graph and b is the number of bits representing a vertex. Using Boolean circuits of prefix computation, odd-even merge, and some other parallel techniques, we present an improved Boolean circuit for the same problem in O(log^2 n · (log b + log log n)) depth and O(bn^2 log n) size. Show more

Keywords: Boolean circuit, convex bipartite graph, maximum matching, prefix computation, ASCEND, odd-even merge

Citation: Fundamenta Informaticae, vol. 84, no. 1, pp. 81-97, 2008

Authors: Lefevre, James G. | Donovan, Diane | Drápal, Aleš

Article Type: Research Article

Abstract: Cavenagh, Donovan and Drápal (2005) gave a construction for 3-homogeneous latin bitrades which was proved by Cavenagh (2006) to give every 3-homogeneous latin bitrade. A corollary is that every 3-homogenous latin bitrade may be partitioned into three disjoint transversals. Using a permutation representation for latin bitrades developed by Drápal, we provide a shorter proof of these results, and then give a construction for a family of separated 4-homogeneous latin bitrades.

Keywords: Latin trade, latin bitrade, homogeneous

Citation: Fundamenta Informaticae, vol. 84, no. 1, pp. 99-110, 2008

Authors: Bueno, Orestes | Manyem, Prabhu

Article Type: Research Article

Abstract: In Descriptive Complexity, there is a vast amount of literature on decision problems, and their classes such as P, NP, L and NL. However, research on the descriptive complexity of optimisation problems has been limited. In a previous paper [13], we characterised the optimisation versions of P via expressions in second order logic, using universal Horn formulae with successor relations. In this paper, we study the syntactic hierarchy within the class of polynomially bound maximisation problems. …We extend the result in the previous paper by showing that the class of polynomially-boundNP (not just P) maximisation problems can be expressed in second-order logic using Horn formulae with successor relations. Finally, we provide an application – we show that the Bin Packing problem with online LIB constraints can be approximated to within a Θ (log n) bound, by providing a syntactic characterisation for this problem. Show more

Keywords: Descriptive Complexity, FiniteModel Theory, Syntactic Hierarchy, Optimization, Quantifier Complexity, Quantifier Alternation, Existential Second Order Logic

Citation: Fundamenta Informaticae, vol. 84, no. 1, pp. 111-133, 2008

Authors: Weng, J.F. | Smith, J. MacGregor | Brazil, M. | Thomas, D.A.

Article Type: Research Article

Abstract: The Steiner tree problem is an intractable optimization problem, which asks for a network, in fact a tree, interconnecting a given point set V in a metric space and minimizing the total length of the network. The tree topology t of the network is called a Steiner topology and a tree T with minimum length with respect to its Steiner topology is called a Steiner tree. As a combinatorial optimization problem, the Steiner tree problem asks for a …Steiner tree T with minimum length over all possible topologies t on V. It has been proved that if T is in E^3 then the length of T cannot be expressed by radicals even when T spans just 4 points. For such optimization problems in which the objective functions do not have closed form solutions the traditional approach is approximation. In this paper we propose a new approach by introducing some new concepts: equivalence, indicators and quasi-indicators, and then we apply these concepts to the Steiner tree problem. Roughly speaking, a quasi-indicator is a function that is simple to compute but indicates with high probability the optimal solution to the original optimisation problem. For a specific optimisation problem – finding the optimal Steiner topologies on 4 points in space, we demonstrate how to find good quasiindicators. The extensive computational experiments over 5000 random 4-point sets show that the best quasi-indicator for finding optimal Steiner topologies on 4 points in space is not only easy to compute but also extremely successful with less than 1.5% failures in indicating optimal topologies even if degeneracy of Steiner minimal trees exists. Moreover, within the 1.5% cases of failure, the maximum and the average relative error are 1.5% and 0.2% respectively. Therefore, the performance of the proposed Q-indicator is very good and could be applied to the four vertices surrounding any pair of adjacent Steiner points in a Steiner tree on n (> 4) points in space to make local improvements to the topology of the Steiner minimal tree in space. Show more

Keywords: equivalence, quasi-indicator, Steiner tree

Citation: Fundamenta Informaticae, vol. 84, no. 1, pp. 135-149, 2008