Fundamenta Informaticae - Volume 162, issue 1

Authors: Dangalchev, Chavdar

Article Type: Research Article

Abstract: One of the most sensitive characteristics of network vulnerability is residual closeness. Calculating the closeness and the residual closeness of larger graphs is a time consuming and operations heavy process. In this article, we try to mitigate the process for thorn graphs - we present the thorn graphs residual closeness as a function of the closeness and the residual closeness of the original graphs.

Keywords: network vulnerability, closeness, residual closeness, thorn graph

DOI: 10.3233/FI-2018-1710

Citation: Fundamenta Informaticae, vol. 162, no. 1, pp. 1-15, 2018

Authors: Dutta, Soma | Wasilewski, Piotr

Article Type: Research Article

Abstract: This paper is an attempt to introduce a notion of dialogue among different agents, e.g. a user or situation descriptor and an information provider or machine, to better understand a user’s need of information. When a user describes a concept through some keywords first the system needs to choose the relevant attributes for initiating the search. Regarding this, a series of dialogues may help the system to better understand the user’s language of expresssion. After fixing the relevant attributes, the system needs to look at its repertoire of positive and negative cases of different concepts characterized with respect to this …set of attributes. Then through a step-by-step process of matching and comparing similarity of user’s described situation with those positive and negative cases of a concept, incorporating several layers of dialogue, the system may provide information closer to the user’s need. The target of this paper is to develop a theoretical model, incorporating the above features, for characterizing one’s concern of concept based on dialogue and similarity based reasoning. Show more

Keywords: Fuzzy approximation space, Prototypes and Counterexamples, Dialogue, Similarity

DOI: 10.3233/FI-2018-1711

Citation: Fundamenta Informaticae, vol. 162, no. 1, pp. 17-36, 2018

Authors: Garg, Manish

Article Type: Research Article

Abstract: Sun and Wu investigated the lower bound of higher-order nonlinearity of the niho Boolean function f ( x ) = T r 1 n ( λ x d ) over ᵓ2n ; where λ ∈ F 2 n * , d = 2 n − 1 2 + 2 3 n − 1 4 − 1 when n ≡ 3 mod 4 in second case of Theorem 3.6 of the paper titled higher-order nonlinearity of niho functions published …in Fundamenta Informaticae 137 (2015) 403–412. Unfortunately, the proof of finding the lower bound of higher-order nonlinearities of the niho Boolean function f (x ) is not correct in the above mentioned paper. In this paper the author gives the correct proof of lower bound of higher-order nonlinearities of the niho Boolean function f (x ). Show more

Keywords: Boolean function, Higher-order derivative, Niho power function, Higher-order nonlinearity, Walsh-spectrum

DOI: 10.3233/FI-2018-1712

Citation: Fundamenta Informaticae, vol. 162, no. 1, pp. 37-42, 2018

Authors: Jeż, Artur | Okhotin, Alexander

Article Type: Research Article

Abstract: Unambiguous conjunctive grammars with 1 nonterminal symbol are shown to be strictly weaker than the grammars with 2 nonterminal symbols, which are in turn strictly weaker that the grammars with 3 or more nonterminal symbols. This hierarchy is established by considering grammars over a one-symbol alphabet, for which it is shown that 1-nonterminal grammars describe only regular languages, 2-nonterminal grammars describe some non-regular languages, but all of them are in a certain sense sparse, whereas 3-nonterminal grammars may describe some non-regular languages of non-zero density. It is also proved that one can test a 2-nonterminal grammar for equivalence with a …regular language, whereas the equivalence between a pair of 2-nonterminal grammars is undecidable. Show more

Keywords: conjunctive grammars, ambiguity, language equations, unary languages, descriptional complexity

DOI: 10.3233/FI-2018-1713

Citation: Fundamenta Informaticae, vol. 162, no. 1, pp. 43-72, 2018

Authors: Sarkar, Apurba | Biswas, Arindam | Dutt, Mousumi | Mondal, Shouvick

Article Type: Research Article

Abstract: This article presents a combinatorial algorithm to find a shortest triangular path (STP) between two points inside a digital object imposed on triangular grid that runs in O ( n g log n g ) time, where n is the number of pixels on the contour of the object and g is the grid size. Initially, the inner triangular cover which maximally inscribes the object is constructed to ensure that the path lies within the object. An appropriate bounding parallelogram is considered with those two points in diagonally opposite corners and then …one of the semi-perimeters of the parallelogram is traversed. Certain combinatorial rules are formulated based on the properties of triangular grid and are applied during the traversal whenever required to shorten the triangular path. A shortest triangular path between any two points may not be unique. Another combinatorial algorithm is presented, which finds the family of shortest triangular path (FSTP) (i.e., the region containing all possible shortest triangular paths) between two given points inside a digital object and runs in O ( n g log n g ) time. Experimental results are presented to verify the correctness, robustness, and efficacy of the algorithms. STP and FSTP can be useful for shape analysis of digital objects and determining shape signatures. 1 Show more

DOI: 10.3233/FI-2018-1714

Citation: Fundamenta Informaticae, vol. 162, no. 1, pp. 73-100, 2018