Fundamenta Informaticae - Volume 137, issue 3

Authors: Fusco, Emanuele G. | Pelc, Andrzej

Article Type: Research Article

Abstract: We consider the message complexity of achieving consensus in synchronous anonymous message passing systems. Unlabeled processors (nodes) communicate through links of a network. An adversary wakes up some subset of processors at possibly different times and assigns them arbitrary numerical input values. All other processors are dormant and do not have input values. Any message wakes up a dormant processor. The goal of consensus is to have all processors agree on one of the input values. We seek deterministic consensus algorithms using as few messages as possible. As opposed to most of the literature on consensus, the difficulty of our …scenario are not faults (we assume that the network is fault-free) but the arbitrary network topology combined with the anonymity of nodes. For n-node networks of unknown topology we show a consensus algorithm using O(n2 ) messages; this complexity is optimal for this class. We show that if the network topology is known, then the complexity of consensus decreases significantly. Our main contribution is an algorithm that uses O(n3/2 log2 n) messages on any n-node network and we show that some networks require Ω(n log n) messages to achieve consensus. Show more

Keywords: algorithm, consensus, anonymous networks, message complexity

DOI: 10.3233/FI-2015-1181

Citation: Fundamenta Informaticae, vol. 137, no. 3, pp. 305-322, 2015

Authors: Hońko, Piotr

Article Type: Research Article

Abstract: Information granulation is a powerful tool for data analysis and processing. However, not much attention has been devoted to application of this tool to data stored in a relational structure. This paper extends the notion of information granules to a relational case. Two information systems intended to store relational data are proposed. This study also extends a granule description language to express information granules derived from relational data. The proposed approach enables to analyze a given problem at different levels of granularity of relational data. This can find application in searching for patterns in data mining.

Keywords: granular computing, relational databases, data mining

DOI: 10.3233/FI-2015-1182

Citation: Fundamenta Informaticae, vol. 137, no. 3, pp. 323-340, 2015

Authors: Järvinen, Jouni | Radeleczki, Sándor

Article Type: Research Article

Abstract: In this paper, we consider tolerances induced by irredundant coverings. Each tolerance R on U determines a quasiorder ≤R by setting x ≤R y if and only if R(x) ⊆ R(y). We prove that for a tolerance R induced by a covering H of U, the covering H is irredundant if and only if the quasiordered set (U,≤R ) is bounded by minimal elements and the tolerance R coincides with the product ≥R º ≤R . We also show that in such a case H = {↑m | m is minimal in (U,≤R )}, and for each …minimal m, we have R(m) = ↑m. Additionally, this irredundant covering H inducing R consists of some blocks of the tolerance R. We give necessary and sufficient conditions under which H and the set of R-blocks coincide. These results are established by applying the notion of Helly numbers of quasiordered sets. Show more

Keywords: Tolerance relation, Irredundant covering, Normal covering, Clique of a graph, Helly number, Rough set, Formal concept analysis

DOI: 10.3233/FI-2015-1183

Citation: Fundamenta Informaticae, vol. 137, no. 3, pp. 341-353, 2015

Authors: Koczkodaj, Waldemar W. | Kosiek, Marek | Szybowski, Jacek | Xu, Ding

Article Type: Research Article

Abstract: This study presents theoretical proof and empirical evidence of the reduction algorithm convergence for the distance-based inconsistency in pairwise comparisons. Our empirical research shows that the convergence very quick. It usually takes less than 10 reductions to bring the inconsistency of the pairwise comparisons matrix below the assumed threshold of 1/3 (sufficient for most applications). We believe that this is the first Monte Carlo study demonstrating such results for the convergence speed of inconsistency reduction in pairwise comparisons.

Keywords: pairwise comparisons, distance-based inconsistency, convergence, knowledge management

DOI: 10.3233/FI-2015-1184

Citation: Fundamenta Informaticae, vol. 137, no. 3, pp. 355-367, 2015

Authors: Kumar, Sachin | Sharma, Rajendra Kumar

Article Type: Research Article

Abstract: The concept of region incrementing in visual cryptography was introduced to encrypt an image into multiple secrecy levels. But, it suffers from the pixel expansion increasing exponentially as the number of participants grows. In this paper, we propose a region incrementing visual secret sharing (RIVSS) scheme based on random grids. The proposed scheme is a general (k, n)-RIVSS scheme, in which any t (k ≤ t ≤ n) shares can be used to reconstruct the secret regions up to t − k + 1 levels. However, no information about the input image can be revealed by any k − 1 …or fewer shares. With a nice property of region incrementing, the proposed scheme benefits by sharing an image without any pixel expansion and codebook requirement. We give formal proofs and experimental results to confirm both correctness and feasibility of our scheme. Show more

Keywords: visual secret sharing, visual cryptography, region incrementing, random grids

DOI: 10.3233/FI-2015-1185

Citation: Fundamenta Informaticae, vol. 137, no. 3, pp. 369-386, 2015

Authors: Marei, Emad A. | Abd El-Monsef, Mohamed E. | Abu-Donia, Hassan M.

Article Type: Research Article

Abstract: Most real life situations need some sort of approximation to fit mathematical models. The beauty of using topology in approximation is achieved via obtaining approximation for qualitative subsets without coding or using assumption. The aim of this paper is to introduce different approaches to near sets by using general relations and special neighborhoods. Some fundamental properties and characterizations are given. We obtain a comparison between these new approximations and traditional approximations introduced by Peters [23].

Keywords: Information system, topological space, rough sets , near sets, β-open set

DOI: 10.3233/FI-2015-1186

Citation: Fundamenta Informaticae, vol. 137, no. 3, pp. 387-402, 2015

Authors: Sun, Guanghong | Wu, Chuankun

Article Type: Research Article

Abstract: The r-th order nonlinearity of Boolean functions is an important cryptographic criterion associated with some attacks on stream and block ciphers. It is also very useful in coding theory, since it is related to the covering radii of Reed-Muller codes. In this paper we investigate the lower bound of the higher-order nonlinearity of Niho Boolean functions f(x) = tr(λxd ) over F2n , where $\lambda \isin F_2_n^*$, $d = 2^{(n-1)/2} + 2^{(n-1)/4} - 1$ when n = 1 mod 4 or $d = 2^{(n-1)/2} + 2^{(3n-1)/4} - 1$ when n = 3 mod 4.

Keywords: Boolean function, cryptography, nonlinearity, derivation, Walsh spectrum, Reed-Muller code

DOI: 10.3233/FI-2015-1187

Citation: Fundamenta Informaticae, vol. 137, no. 3, pp. 403-412, 2015

Authors: Umadevi, Dwaraganathan

Article Type: Research Article

Abstract: In this paper, a solution is given to the problem proposed by Järvinen in [8]. A smallest completion of the rough sets system determined by an arbitrary binary relation is given. This completion, in the case of a quasi order, coincides with the rough sets system which is a Nelson algebra. Further, the algebraic properties of this completion has been studied.

Keywords: Poset, complete lattice, completion of a poset, rough sets

DOI: 10.3233/FI-2015-1188

Citation: Fundamenta Informaticae, vol. 137, no. 3, pp. 413-424, 2015