Fundamenta Informaticae - Volume 156, issue 2

Authors: Avesalon, Nicoleta | Ciurea, Eleonor | Parpalea, Mircea

Article Type: Research Article

Abstract: This article states and solves the maximum parametric flow over time problem. The proposed approach consists in repeatedly finding the maximum dynamic flow in discrete dynamic networks, for a sequence of parameter values, in their increasing order. In each of its iterations, the algorithm computes both the maximum flow, by minimizing the transit time (quickest flow), and the new breakpoint for the maximum parametric dynamic flow value function. The dynamic flow is augmented along quickest paths from the source node to the sink node in the time-space network, avoiding the explicit time expansion of the network. The complexity of the …algorithm is presented and also an example is given on how the algorithm works. Show more

Keywords: Dynamic networks, parametric flow, successive shortest paths

DOI: 10.3233/FI-2017-1600

Citation: Fundamenta Informaticae, vol. 156, no. 2, pp. 125-139, 2017

Authors: Bartl, Eduard | Konecny, Jan

Article Type: Research Article

Abstract: We provide a new approach to fusion of Fuzzy Formal Concept Analysis and Rough Set Theory. As a starting point we take into account a couple of fuzzy relations, one of them represents the lower approximation, while the other one the upper approximation of a given data table. By defining appropriate concept-forming operators we transfer the roughness of the input data table to the roughness of corresponding formal fuzzy concepts in the sense that a formal fuzzy concept is considered as a collection of objects accompanied with two fuzzy sets of attributes—those which are shared by all the objects and …those which at least one object has. In the paper we study the properties of such formal concepts and show their relationship with concepts formed by well-known isotone and antitone operators. Show more

Keywords: antitone concept-forming operator, concept lattice, formal concept analysis, Galois connection, isotone concept-forming operator, rough set, truth-depressing hedge, truth-stressing hedge

DOI: 10.3233/FI-2017-1601

Citation: Fundamenta Informaticae, vol. 156, no. 2, pp. 141-168, 2017

Authors: Csató, László

Article Type: Research Article

Abstract: It has been shown recently that the Eigenvector Method may lead to strong rank reversal in group decision making, that is, the alternative with the highest priority according to all individual vectors may lose its position when evaluations are derived from the aggregated group comparison matrix. We give a minimal counterexample and prove that this negative result is a consequence of the difference of the rankings induced by the right and inverse left eigenvectors.

Keywords: preference aggregation, pairwise comparison matrix, axiomatic approach, rank reversal, Eigenvector Method

DOI: 10.3233/FI-2017-1602

Citation: Fundamenta Informaticae, vol. 156, no. 2, pp. 169-178, 2017

Authors: Durnoga, Konrad | Pomykała, Jacek

Article Type: Research Article

Abstract: G. Miller in his seminal paper from the mid 1970s has proven that the problem of factoring integers reduces to computing Euler’s totient function φ under the Extended Riemann Hypothesis. We show, unconditionally, that such a deterministic polynomial reduction exists for a large class of integers.

Keywords: large sieve, factoring algorithms, ℤn*-generating sets, Dirichlet characters, smooth numbers, Discrete Logarithm Problem for Composite Numbers

DOI: 10.3233/FI-2017-1603

Citation: Fundamenta Informaticae, vol. 156, no. 2, pp. 179-185, 2017

Authors: Su, Yansen | Wu, Tingfang | Xu, Fei | Păun, Andrei

Article Type: Research Article

Abstract: Spiking neural P systems with rules on synapses (RSSN P systems, for short) are a class of distributed and parallel computation models inspired by the way in which neurons process and communicate information with each other by means of spikes, where neurons only contain spikes and the evolution rules are on synapses. RSSN P systems have been proved to be Turing universal, using the strategy that restricts all the applied rules to consume the same number of spikes from the given neuron, termed as equal spikes consumption strategy . In this work, in order to avoid imposing the equal spikes …consumption restriction on the application of rules, a new strategy for rule application, termed as sum spikes consumption strategy , is considered in RSSN P systems, where a maximal set of enabled rules from synapses starting from the same neuron is nondeterministically chosen to be applied, in the sense that no further synapse can use any of its rules, and the sum of these numbers of spikes that all the applied rules consume is removed from the neuron. In this way, the proposed strategy avoids checking whether all the applied rules consume the same number of spikes from the given neuron. The computation power of RSSN P systems working in the proposed strategy is investigated, and it is proved that such systems characterize the semilinear sets of natural numbers, i.e., such systems are not universal. Furthermore, RSSN P systems with weighted synapses working in the proposed strategy are proved to be Turing universal. These results show that the weight on synapses is a powerful ingredient of RSSN P systems in terms of the computation power, which makes RSSN P systems working in sum spikes consumption strategy become universal from non-universality. Show more

Keywords: Bio-inspired computing, Membrane computing, Spiking neural network, Spiking neural P system, Universality

DOI: 10.3233/FI-2017-1604

Citation: Fundamenta Informaticae, vol. 156, no. 2, pp. 187-208, 2017

Authors: Varish, Naushad | Kumar, Sumit | Pal, Arup Kumar

Article Type: Research Article

Abstract: Content-based image retrieval (CBIR) scheme has gained popularity in the field of information retrieval for retrieving some relevant images from the image database based on the visual descriptors such as color, texture and/or shape of a given query image. In this paper, color features have been exploited from each color component of an RGB color image by using multi-resolution approach since most of the information of an image is undetected at one resolution level while some other undetectable information is visualized in other multi-resolution levels. Initially, Gaussian image pyramid is employed on each color component of the color image and …subsequent DCT is computed directly on the obtained multi-resolution image planes. Then some significant DCT coefficients are selected according to the zigzag scanning order. For formation of the feature vector, we have derived some statistical values from AC coefficients and all other DC coefficients are included entirely. Finally, a similarity measure is suggested during image retrieval process and it is found that the overall computation overhead is reduced due to consideration of the proposed similarity measure. The proposed CBIR scheme is validated on a two standard Corel-1K and GHIM-10K image databases and satisfactory results are achieved in terms of precision, recall and F-score. The retrieved results show that the proposed scheme outperforms significantly over other related CBIR schemes. Show more

Keywords: Content Based Image Retrieval, DCT, Feature Extraction, Gaussian Image Pyramid, Similarity Measure

DOI: 10.3233/FI-2017-1605

Citation: Fundamenta Informaticae, vol. 156, no. 2, pp. 209-235, 2017

Authors: Wang, Jingqian | Zhu, William

Article Type: Research Article

Abstract: In this paper, bipartite graphs and their adjacency matrices are applied to equivalently represent covering-based rough sets through three sides, which are approximation operators, properties and reducible elements. Firstly, a bipartite graph is constructed through a covering. According to the constructed bipartite graph, two equivalent representations of a pair of covering upper and lower approximation operators are presented. And an algorithm is designed for computing the pair of covering approximation operators from the viewpoint of these equivalent representations. Some properties and reducible elements of covering-based rough sets are also investigated through the constructed bipartite graph. Finally, an adjacency matrix of …the constructed bipartite graph is proposed, and reducible elements in the covering are obtained through the proposed adjacency matrix. Moreover, an equivalent representation of the covering upper approximation operator is presented through the proposed adjacency matrix. In a word, these results show two interesting views, which are graphs and matrices, to investigate covering-based rough sets. Show more

Keywords: Approximation operator, Adjacency matrix, Bipartite graph, Covering, Covering-based rough set

DOI: 10.3233/FI-2017-1606

Citation: Fundamenta Informaticae, vol. 156, no. 2, pp. 237-254, 2017