Fundamenta Informaticae - Volume 129, issue 4

Authors: Balbiani, Philippe | Tinchev, Tinko

Article Type: Research Article

Abstract: This paper studies the concepts of definability and canonicity in Boolean logic with a binary relation. Firstly, it provides formulas defining first-order or second-order conditions on frames. Secondly, it proves that all formulas corresponding to compatible first-order conditions on frames are canonical.

Keywords: Boolean algebra, modal logic, definability, canonicity

DOI: 10.3233/FI-2014-973

Citation: Fundamenta Informaticae, vol. 129, no. 4, pp. 301-327, 2014

Authors: Chowdhury, Shihabur Rahman | Hasan, Md. Mahbubul | Iqbal, Sumaiya | Rahman, M. Sohel

Article Type: Research Article

Abstract: The longest common subsequence (LCS) problem is a classic and well-studied problem in computer science. Palindrome is a word which reads the same forward as it does backward. The longest common palindromic subsequence (LCPS) problem is a variant of the classic LCS problem which finds a longest common subsequence between two given strings such that the computed subsequence is also a palindrome. In this paper, we study the LCPS problem and give two novel algorithms to solve it. To the best of our knowledge, this is the first attempt to study and solve this problem.

Keywords: longest common subsequence, palindromes, dynamic programming, range query

DOI: 10.3233/FI-2014-974

Citation: Fundamenta Informaticae, vol. 129, no. 4, pp. 329-340, 2014

Authors: Szczuka, Marcin | Sosnowski, Łukasz | Krasuski, Adam | Kreński, Karol

Article Type: Research Article

Abstract: We present a set of guidelines for improving quality and efficiency in initial steps of the KDD process by utilizing various kinds of domain knowledge. We discuss how such knowledge may be used to the advantage of system developer and what kinds of improvements can be achieved. We focus on systems that incorporate creation and processing of compound data objects within the RDBMS framework. These basic considerations are illustrated with several examples of implemented database solutions.

Keywords: Domain knowledge, KDD process, database sharding, hierarchical systems, compound data objects, data cleansing

DOI: 10.3233/FI-2014-975

Citation: Fundamenta Informaticae, vol. 129, no. 4, pp. 341-364, 2014

Authors: Tian, Miaomiao | Yang, Wei | Huang, Liusheng

Article Type: Research Article

Abstract: Certificateless cryptography is a new type of public key cryptography, which removes the certificate management problem in traditional public key cryptography and the key escrow problem in identity-based public key cryptography. Multi-proxy signature is an extension of proxy signature, which allows an original signer authorizing a group of proxy signers and only the cooperation of all proxy signers in the group can create valid proxy signatures on behalf of the original signer. Recently, Jin and Wen combined certificateless cryptography with multi-proxy signature, and proposed a model as well as a concrete scheme of certificateless multi-proxy signature. They claimed that their …scheme is provably secure in their security model. Unfortunately, in this paper by giving two attacks, we will show that their certificateless multi-proxy signature scheme can be broken. The first attack indicates their security model is flawed and the second attack indicates their certificateless multi-proxy signature scheme is insecure. Possible improvements are also suggested to prevent these attacks. Show more

Keywords: cryptanalysis, certificateless cryptography, multi-proxy signature, bilinear pairing

DOI: 10.3233/FI-2013-976

Citation: Fundamenta Informaticae, vol. 129, no. 4, pp. 365-375, 2014

Authors: Wang, Shiping | Zhu, Qingxin | Zhu, William | Min, Fan

Article Type: Research Article

Abstract: Rough sets are efficient to extract rules from information systems. Matroids generalize the linear independency in vector spaces and the cycle in graphs. Specifically, matroids provide well-established platforms for greedy algorithms, while most existing algorithms for many rough set problems including attribute reduction are greedy ones. Therefore, the combination between rough sets and matroids may bring new efficient solutions to those important and difficult problems. In this paper, 2-circuit matroids, abstracted from matroidal characteristics of rough sets, are studied and axiomatized. A matroid is induced by an equivalence relation, and its characteristics including the independent set and duality are represented …with rough sets. Based on these rough set representations, this special type of matroid is defined as 2-circuit matroids. Conversely, an equivalence relation is induced by a matroid, and its relationship with the above induction is further investigated. Finally, a number of axioms of the 2-circuit matroid are obtained through rough sets. These interesting and diverse axioms demonstrate the potential for the connection between rough sets and matroids. Show more

Keywords: Rough set, matroid, 2-circuit matroid, duality, restriction, contraction

DOI: 10.3233/FI-2013-977

Citation: Fundamenta Informaticae, vol. 129, no. 4, pp. 377-393, 2014

Authors: You, Lin | Yang, Yilin | Gao, Shuhong | Sang, Yongxuan

Article Type: Research Article

Abstract: Hyperelliptic curves have been widely researched for cryptographic applications, and some special hyperelliptic curves are often considered for practical applications. For efficient implementation of hyperelliptic curve cryptosystems, it is crucial to have efficient scalar multiplication in the Jacobian groups. For the hyperelliptic curve Cq : v2 = up − au − b over the field $\Fopf_{q}$ with q a power of an odd prime p, Duursma and Sakurai (2000) presented a scalar multiplication algorithm for q = p, a = 1 and b ∈ $\Fopf_{p}$. In this paper, by introducing the concept of simple divisors, we prove that …a general divisor can be decomposed into the sum of some simple divisors. Based on this fact, we present a formula for p-scalar multiplications for any reduced divisor, then we give two efficient algorithms to speed up scalar multiplications for any parameters a and b over any extension of $\Fopf_{p}$. Compared with the signed binary method, the computations of our algorithms cost 55% to 76% less. Show more

Keywords: Hyperelliptic curve, Cryptosystem, Scalar Multiplications, Divisor, Jacobian Group

DOI: 10.3233/FI-2014-978

Citation: Fundamenta Informaticae, vol. 129, no. 4, pp. 395-412, 2014

Article Type: Other

Citation: Fundamenta Informaticae, vol. 129, no. 4, pp. 413-414, 2014