Fundamenta Informaticae - Volume 76, issue 1-2

Authors: Busch, J.

Article Type: Research Article

Abstract: We establish lower bounds on the complexity of computing the following number-theoretic functions and relations from piecewise linear primitives: (i) the Legendre and Jacobi symbols, (ii) pseudoprimality, and (iii) modular exponentiation. As a corollary to the lower bound obtained for (i), an algorithm of Shallit and Sorenson is optimal (up to a multiplicative constant).

Keywords: arithmetic complexity, computational complexity, Jacobi symbol, lower bounds

Citation: Fundamenta Informaticae, vol. 76, no. 1-2, pp. 1-11, 2007

Authors: Chang, Ya-Fen | Chang, Chin-Chen

Article Type: Research Article

Abstract: In 1998, Yeh et al. proposed a flexible key assignment scheme for enforcing complicated access control policies in a user matrix model. Later, Hwang indicated that Yeh et al.' scheme is susceptible to some security flaws. Thus, Lin et al. proposed a key assignment scheme for enforcing complicated access control policies in a hierarchy. However, there exist drawbacks in Lin et al.'s scheme: lack of efficiency and a large variation of the keys. Hence, we propose …an efficient key assignment scheme in a hierarchy for enforcing the complicated access control policies. What is more, the secret key of one class is allowed to be changed several times without influencing the derivation key in our proposed scheme. Show more

Keywords: key assignment, hierarchy, access control

Citation: Fundamenta Informaticae, vol. 76, no. 1-2, pp. 13-23, 2007

Authors: Chang, Chin-Chen | Chen, Chang-Chu

Article Type: Research Article

Abstract: The encoding process of vector quantization (VQ) is indeed computational complex and time consuming. Compared with actual Euclidean distance computation, some inequalities can generate estimations with less computation to filter out the impossible codevectors as well as to reduce the computation time. In this paper, we introduce a new estimation for the Euclidean distance using two-bounds triangle inequality. The experimental results show that our proposed scheme can reduce Euclidean distance computation by …71% to 94% for full search. Having been proved, our proposed scheme can reduce the computing time by 42% to 51%. Show more

Keywords: Full-searching-equivalent, triangle inequality, vector quantization (VQ)

Citation: Fundamenta Informaticae, vol. 76, no. 1-2, pp. 25-37, 2007

Authors: Chang, Chin-Chen | Lu, Tzu-Chuen | Ya, Jun-Bin

Article Type: Research Article

Abstract: In this paper, we shall present two efficient codebook-matching schemes with a locally adaptive vector quantizer (LAVQ) and a search-ordering coding vector quantizer (SOCVQ) to be applied in the Vector Quantization (VQ) encoding system. The proposed codebook-matching schemes exploit the correlation property between adjacent image blocks so that the process of codebook matching can be speed up. Simulation results show that the time complexity of the proposed schemes is lower than those of PCA, Multipath TSVQ, …and DPTSVQ. Moreover, the image quality of the proposed methods is close to those processed by the other methods. Show more

Keywords: Vector quantization, locally adaptive approach, search-ordering coding, codebook matching

Citation: Fundamenta Informaticae, vol. 76, no. 1-2, pp. 39-57, 2007

Authors: Chunlin, Li | Layuan, Li

Article Type: Research Article

Abstract: The paper is targeted at concerning pricing approach for grid resource scheduling with QoS guarantees. The two major parties in Grid, namely, resource consumers who submit various applications, and resources providers who share their resources, usually have different motivations when they join the Grid. These incentives are presented by objective functions in scheduling. Economic grid QoS scheduling algorithm adopt both application-centric and resource-centric scheduling objective function aim to optimize the performance of …each individual grid user and the performance of the grid resources. The economic cost and profit are considered by grid users and resource providers respectively. Objective functions and QoS scheduling optimization algorithms are proposed. QoS scheduling optimization is decomposed into two sub optimizations of grid user's cost and grid resource provider's profit by utilizing dynamic programming. QoS scheduling algorithm is an interactive process in economic market coordinating grid users and grid resource providers to achieve optimal QoS scheduling. Experiments are to compare the proposed economic QoS scheduling with three partial optimisation approaches, which only consider one criterion. Show more

Keywords: economic scheduling, QoS, grid

Citation: Fundamenta Informaticae, vol. 76, no. 1-2, pp. 59-73, 2007

Authors: Dey, Sabyasachi | Bhattacharya, Bhargab B. | Kundu, Malay K. | Bishnu, Arijit | Acharya, Tinku

Article Type: Research Article

Abstract: Euler number is a fundamental topological feature of an image. The efficiency of computation of topological features of an image is critical for many digital imaging applications such as image matching, database retrieval, and computer vision that require real time response. In this paper, a novel algorithm for computing the Euler number of a binary image based on divide-andconquer paradigm, is proposed, which outperforms significantly the conventional techniques used in image processing tools. The algorithm can …be easily parallelized for computing the Euler number of an N × N image in O(N) time, with O(N) processors. Using a simple architecture, the proposed method can be implemented as a special purpose VLSI chip to be used as a co-processor. Show more

Keywords: Binary image, digital imaging, Euler number, VLSI

Citation: Fundamenta Informaticae, vol. 76, no. 1-2, pp. 75-89, 2007

Authors: Formenti, Enrico | Masson, Benoît | Pisokas, Theophilos

Article Type: Research Article

Abstract: A symmetric version of the well-known SPM model for sandpiles is introduced. We prove that the new model has fixed-point dynamics. Although there might be several fixed points, a precise description of the fixed points is given. Moreover, we provide a simple closed formula for counting the number of fixed points originated by initial conditions made of a single column of grains. Bounds for the transient length are also given.

Keywords: discrete dynamical systems, SOC systems, sandpiles, fixed point dynamics, transient length

Citation: Fundamenta Informaticae, vol. 76, no. 1-2, pp. 91-112, 2007

Authors: Han, Yo-Sub | Salomaa, Kai | Wood, Derick

Article Type: Research Article

Abstract: Intercodes are a generalization of comma-free codes. Using the structural properties of finite-state automata recognizing an intercode we develop a polynomial-time algorithm for determining whether or not a given regular language L is an intercode. If the answer is yes, our algorithm yields also the smallest index k such that L is a k-intercode. Furthermore, we examine the prime intercode decomposition of intercode regular languages and design an algorithm for the intercode primality test …of an intercode recognized by a finite-state automaton. We also propose an algorithm that computes the prime intercode decomposition of an intercode regular language in polynomial time. Finally, we demonstrate that the prime intercode decomposition need not be unique. Show more

Keywords: regular languages, finite-state automata, intercodes, state-pair graphs, prime decompositions

Citation: Fundamenta Informaticae, vol. 76, no. 1-2, pp. 113-128, 2007

Authors: Järvinen, Jouni | Kondo, Michiro | Kortelainen, Jari

Article Type: Research Article

Abstract: In this work, four modal-like operators on Boolean lattices are introduced and their theory is presented from lattice-theoretical, topological and algebraic point of view. It is also shown how rough set approximation operators, modal operators in temporal logic, and linguistic modifiers determined by L-sets can be interpreted as modal-like operators.

Keywords: Galois connections, Closure operators, Fixed points, Boolean lattices with additional operators

Citation: Fundamenta Informaticae, vol. 76, no. 1-2, pp. 129-145, 2007

Authors: Paquet, Ulrich | Engelbrecht, Andries P.

Article Type: Research Article

Abstract: Particle Swarm Optimisation (PSO) has proved to be a very useful algorithm to optimise unconstrained functions. This paper extends PSO to a Linear PSO (LPSO) to optimise functions constrained by a set of equality constraints of the form Ax=b. By initialising particles within a constrained hyperplane, the LPSO is guaranteed to 'fly' only through this hyperplane. A criterion on the initial swarm stipulates when the optimum solution can possibly be reached. The Linear PSO is modified …to the Converging Linear PSO, for which it is proved to always find at least a local minimum. Experimental results are given, which compare the LPSO and CLPSO with Genocop II. Show more

Keywords: Particle Swarm Optimisation, Constrained Optimisation, Convergence Proofs

Citation: Fundamenta Informaticae, vol. 76, no. 1-2, pp. 147-170, 2007

Authors: Saha, Suman | Murthy, C.A. | Pal, Sankar K.

Article Type: Research Article

Abstract: Combining the results of a number of individually trained classification systems to obtain a more accurate classifier is a widely used technique in pattern recognition. In this article, we have introduced a rough set based meta classifier to classify web pages. The proposed method consists of two parts. In the first part, the output of every individual classifier is considered for constructing a decision table. In the second part, rough set attribute reduction and rule generation …processes are used on the decision table to construct a meta classifier. It has been shown that (1) the performance of the meta classifier is better than the performance of every constituent classifier and, (2) the meta classifier is optimal with respect to a quality measure defined in the article. Experimental studies show that the meta classifier improves accuracy of classification uniformly over some benchmark corpora and beats other ensemble approaches in accuracy by a decisive margin, thus demonstrating the theoretical results. Apart from this, it reduces the CPU load compared to other ensemble classification techniques by removing redundant classifiers from the combination. Show more

Keywords: Text classification, Rough set, Meta classifier

Citation: Fundamenta Informaticae, vol. 76, no. 1-2, pp. 171-187, 2007

Authors: Tarasyuk, Igor V.

Article Type: Research Article

Abstract: In the last decades, a number of stochastic enrichments of process algebras was constructed to allow one for specification of stochastic processes within the well-developed framework of algebraic calculi. In [40], a continuous time stochastic extension of finite Petri box calculus (PBC) was proposed called sPBC. The algebra sPBC has interleaving semantics due to the properties of continuous time distributions. At the same time, PBC has step semantics, and it could be natural to propose its …concurrent stochastic enrichment. We construct a discrete time stochastic extension dtsPBC of finite PBC. A step operational semantics is defined in terms of labeled transition systems based on action and inaction rules. A denotational semantics is defined in terms of a subclass of labeled discrete time stochastic Petri nets (LDTSPNs) called discrete time stochastic Petri boxes (dts-boxes). A consistency of both semantics is demonstrated. In addition, we define a variety of probabilistic equivalences that allow one to identify stochastic processes with similar behaviour which are differentiated by too strict notion of the semantic equivalence. The interrelations of all the introduced equivalences are investigated. Show more

Keywords: Stochastic Petri nets, stochastic process algebras, Petri box calculus, discrete time, transition systems, operational semantics, dts-boxes, denotational semantics, empty loops, probabilistic equivalences

Citation: Fundamenta Informaticae, vol. 76, no. 1-2, pp. 189-218, 2007