Fundamenta Informaticae - Volume 153, issue 3

Authors: Chai, Ming | Schlingloff, Bernd-Holger

Article Type: Research Article

Abstract: Runtime verification is a lightweight formal method that checks whether an execution of a system satisfies a given property. A challenge in building a runtime verification system is to define a suitable monitoring specification language, i.e., a language that is expressive, of reasonable complexity, and easy to understand. In this paper, we extend live sequence charts (LSCs, [1]) for the specification of properties in systems monitoring. We define Parametrized extended LSCs (PeLSCs) by introducing the notions of necessary prechart, concatenation, and condition- and assignment-structure. With these PeLSCs, necessary and sufficient conditions of certain observations, and parametric properties can be specified …in an intuitive way. We prove some results about the expressiveness of extended LSCs. In particular, we show that LSCs with necessary precharts are strictly more expressive than standard LSCs, and that iteration-free extended LSCs have the same expressive power as linear temporal logic (LTL). To generate monitors, we develop translations of PeLSCs into hybrid logic. We show that the complexity of the word problem of PeLSCs is linear with respect to the length of input traces, thus our formalism is well-suited for online monitoring of communicating systems. Show more

Keywords: Runtime verification, Live sequence charts, Parameterized property, LTL, Hybrid logic

DOI: 10.3233/FI-2017-1536

Citation: Fundamenta Informaticae, vol. 153, no. 3, pp. 173-198, 2017

Authors: Chlebus, Bogdan S. | De Marco, Gianluca | Talo, Muhammed

Article Type: Research Article

Abstract: We consider a communication channel in which the only available mode of communication is transmitting beeps. A beep transmitted by a station attached to the channel reaches all the other stations instantaneously. Stations are anonymous, in that they do not have any individual identifiers. The algorithmic goal is to assign names to the stations in such a manner that the names make a contiguous segment of positive integers starting from 1. We develop a Las Vegas naming algorithm, for the case when the number of stations n is known, and a Monte Carlo algorithm, for the case when the …number of stations n is not known. The given randomized algorithms are provably optimal with respect to the expected time 𝒪(n log n ), the expected number of used random bits 𝒪(n log n ), and the probability of error. Show more

Keywords: beeping channel, anonymous network, randomized algorithm, Las Vegas algorithm, Monte Carlo algorithm, lower bound

DOI: 10.3233/FI-2017-1537

Citation: Fundamenta Informaticae, vol. 153, no. 3, pp. 199-219, 2017

Authors: Denisiuk, Aleksander | Grabowski, Michał

Article Type: Research Article

Abstract: In this article we propose a new clustering algorithm for combinations of continuous and nominal data. The proposed algorithm is based on embedding of the nominal data into the unit sphere with a quadrance metrics, and adaptation of the general k-means clustering algorithm for the embedding data. It is also shown that the distortion of new embedding with respect to the Hamming metrics is less than that of other considered possibilities. A series of numerical experiments on real and synthetic datasets show that the proposed algorithm provide a comparable alternative to other clustering algorithms for combinations of continuous and …nominal data. Show more

DOI: 10.3233/FI-2017-1538

Citation: Fundamenta Informaticae, vol. 153, no. 3, pp. 221-233, 2017

Authors: Joshi, Himani | Arora, Sankalap

Article Type: Research Article

Abstract: Grey Wolf Optimizer (GWO) is a new meta-heuristic search algorithm inspired by the social behavior of leadership and the hunting mechanism of grey wolves. GWO algorithm is prominent in terms of finding the optimal solution without getting trapped in premature convergence. In the original GWO, half of the iterations are dedicated to exploration and the other half are devoted to exploitation, overlooking the impact of right balance between these two to guarantee an accurate approximation of global optimum. To overcome this shortcoming, an Enhanced Grey Wolf Optimization (EGWO) algorithm with a better hunting mechanism is proposed, which focuses on proper …balance between exploration and exploitation that leads to an optimal performance of the algorithm and hence promising candidate solutions are generated. To verify the performance of our proposed EGWO algorithm, it is benchmarked on twenty-five benchmark functions with diverse complexities. It is then employed on range based node localization problem in wireless sensor network to demonstrate its applicability. The simulation results indicate that the proposed algorithm is able to provide superior results in comparison with some well-known algorithms. The results of the node localization problem indicate the effectiveness of the proposed algorithm in solving real world problems with unknown search spaces. Show more

Keywords: Grey wolf optimizer (GWO), Global optimization, Exploration, Exploitation, Wireless sensor network, Node localization

DOI: 10.3233/FI-2017-1539

Citation: Fundamenta Informaticae, vol. 153, no. 3, pp. 235-264, 2017

Authors: Koprowski, Przemysław

Article Type: Research Article

Abstract: We show a method for constructing a polynomial interpolating roots’ multiplicities of another polynomial, that does not use companion matrices. This leads to a modification to Guersenzvaig–Szechtman square-free decomposition algorithm that is more efficient both in theory and in practice.

Keywords: square-free factorization, companion matrix

DOI: 10.3233/FI-2017-1540

Citation: Fundamenta Informaticae, vol. 153, no. 3, pp. 265-270, 2017

Authors: Syau, Yu-Ru | Lin, En-Bing | Liau, Churn-Jung

Article Type: Research Article

Abstract: In this paper, we present the connection between the concepts of Variable Precision Generalized Rough Set model (VPGRS-model) and Neighborhood Systems through binary relations. We provide characterizations of lower and upper approximations for VPGRS-model by introducing minimal neighborhood systems. Furthermore, we explore generalizations by investigating variable parameters which are limited by variable precision. We also prove some properties of lower and upper approximations for VPGRS-model.

Keywords: Neighborhood systems, rough sets, variable precision rough sets, variable precision generalized rough sets, lower and upper approximations

DOI: 10.3233/FI-2017-1541

Citation: Fundamenta Informaticae, vol. 153, no. 3, pp. 271-290, 2017