Fundamenta Informaticae - Volume 152, issue 1

Authors: Basu, Nilanjana G. | Majumder, Subhashis | Hon, Wing Kai

Article Type: Research Article

Abstract: Finding the density of a set of n points, especially where points are in IR 2 or IR 3 , has direct applications in thermal analysis of VLSI chips. In this paper, we consider identifying the maximum-density axes-parallel region for a set of weighted points in IR d for d ≥ 2, and show that it can be done in O (dn 2 ) time. We also consider finding the minimum-density axes-parallel region, and show that for IR 2 the problem can be solved in O (n 2 ) time.

Keywords: MER, density, Axes-parallel

DOI: 10.3233/FI-2017-1509

Citation: Fundamenta Informaticae, vol. 152, no. 1, pp. 1-12, 2017

Authors: Chakraverty, Snehashish | Hladík, Milan | Mahato, Nisha Rani

Article Type: Research Article

Abstract: This paper deals with solving interval system of linear equations. The problem is to find a nonnegative algebraic solution. Based on sign function approach and using interval center and radius arithmetic operations, we propose an algorithm for computation of an algebraic interval solution vector. We also discuss fundamental properties of this solution vector, such as existence and uniqueness. Further, the nonnegative solution algorithm has been extended to other sign-restricted approach. Numerical examples of interval system of linear equations show efficiency of the algorithms presented.

Keywords: Interval matrix, Interval analysis, Linear system of equations, Linear interval systems, Nonnegative solution

DOI: 10.3233/FI-2017-1510

Citation: Fundamenta Informaticae, vol. 152, no. 1, pp. 13-31, 2017

Authors: Kheirfam, Behrouz

Article Type: Research Article

Abstract: In this paper, we propose a predictor-corrector infeasible interior-point algorithm for semidefinite optimization based on the Nesterov-Todd scaling scheme. In each iteration, the algorithm computes the new iterate using a new combination of the predictor and corrector directions. Using the Ai-Zhang’s wide neighborhood for linear complementarity problems, and extended to semidefinite optimization by Li and Terlaky, it is shown that the iteration complexity bound of the algorithm is 𝒪 ( n 5 4 log ε − 1 ) , where n is the dimension of the problem and ɛ …is the required precision. Show more

Keywords: Semidefinite optimization, wide neighborhood, infeasible-interior-point method, predictor-corrector method, polynomial complexity

DOI: 10.3233/FI-2017-1511

Citation: Fundamenta Informaticae, vol. 152, no. 1, pp. 33-50, 2017

Authors: Meduna, Alexander | Soukup, Ondřej

Article Type: Research Article

Abstract: Conceptually, jumping scattered context grammars coincide with their standard counterparts, but they work differently. Indeed, a jumping version can apply a rule of the form (A 1 , A 2 , . . . , A n ) → (x 1 , x 2 , . . . , x n ) so it simultaneously erases A 1 , A 2 , . . . , A n in the current sentential form while inserting x 1 , x 2 , . . . , x n possibly at different positions than the erased …nonterminals. In fact, this paper introduces and studies scattered context grammars working under nine different jumping derivation modes, all of which give rise to the computational completeness. Indeed, the paper characterize the family of recursively enumerable languages by scattered context grammars working under any of these jumping modes. In its conclusion, the paper sketches application perspectives and formulates several open problems. Show more

Keywords: scattered context grammars, jumping derivation modes, generative power, computational completeness

DOI: 10.3233/FI-2017-1512

Citation: Fundamenta Informaticae, vol. 152, no. 1, pp. 51-86, 2017

Authors: Shin, Kilho

Article Type: Research Article

Abstract: Determining whether convolution and mapping kernels are always infinitely divisible has been an unsolved problem. The mapping kernel is an important class of kernels and is a generalization of the well-known convolution kernel. The mapping kernel has a wide range of application. In fact, most of kernels known in the literature for discrete data such as strings, trees and graphs are mapping (convolution) kernels including the q -gram and the all-sub-sequence kernels for strings and the parse-tree and elastic kernels for trees. On the other hand, infinite divisibility is a desirable property of a kernel, which claims that the c …-th power of the kernel is positive definite for arbitrary c ∈ (0, ∞). This property is useful in practice, because the c -th power of the kernel may have better power of classification when c is appropriately small. This paper shows that there are infinitely many positive definite mapping kernels that are not infinitely divisible. As a corollary to this discovery, the q -gram, all-sub-sequence, parse-tree or elastic kernel turns out not to be infinitely divisible. Although these are a negative result, we also show a method to approximate the c -th power of a kernel with a positive definite kernel under certain conditions. Show more

Keywords: kernel, infinite divisibility

DOI: 10.3233/FI-2017-1513

Citation: Fundamenta Informaticae, vol. 152, no. 1, pp. 87-105, 2017