Fundamenta Informaticae - Volume 131, issue 2

Authors: Chang, Chin-Chen | Cheng, Ting-Fang

Article Type: Research Article

Abstract: With the rapid development of network technologies and the continuing growth of the online population, the distribution of streamed media on the Internet has become a cause for concern. In order to securely deliver large-scale message streams, various multicast authentication protocols have been proposed. Recently, Abdellatif et al. proposed a real-time multicast authentication protocol called LAR1. The LAR1 protocol has low computation and communication overheads and uses the erasure code function to deal with the packet loss problem. However, through careful analyses, we find that their scheme cannot resist impersonation attacks on signers and only partially solves the packet loss …problem. Moreover, there are still some design weaknesses. Then, we propose a more secure multicast authentication protocol, called IMA, with almost the same computation overheads and lower communication overheads. We adopt the BAN logic to demonstrate the authentication accuracy of our proposed scheme. Comparisons of other related works show that our proposed IMA protocol maintains efficiency and is more secure. Therefore, our proposed protocol is more suitable for practical applications. Show more

Keywords: authentication, multicast, impersonation attack, BAN logic, confidentiality, non-repudiation

DOI: 10.3233/FI-2014-1008

Citation: Fundamenta Informaticae, vol. 131, no. 2, pp. 167-186, 2014

Authors: Egidi, Lavinia | Manzini, Giovanni

Article Type: Research Article

Abstract: A widely used class of approximate pattern matching algorithms work in two stages, the first being a filtering stage that uses spaced seeds to quickly discards regions where a match is not likely to occur. The design of effective spaced seeds is known to be a hard problem. In this setting, we propose a family of lossless spaced seeds for matching with up to two errors based on mathematical objects known as perfect rulers. We analyze these seeds with respect to the tradeoff they offer between seed weight and the minimum length of the pattern to be matched. We identify …a specific property of rulers, namely their skewness, which is closely related to the minimum pattern length of the derived seeds. In this context, we study in depth the specific case of Wichmann rulers and investigate the generalization of our approach to the larger class of unrestricted rulers. Although our analysis is mainly of theoretical interest, we show that for pattern lengths of practical relevance our seeds have a larger weight, hence a better filtration efficiency, than the ones known in the literature. Show more

DOI: 10.3233/FI-2014-1009

Citation: Fundamenta Informaticae, vol. 131, no. 2, pp. 187-203, 2014

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

Article Type: Research Article

Abstract: The theory of rough sets provides a widely used modern tool, and in particular, rough sets induced by quasiorders are in the focus of the current interest, because they are strongly interrelated with the applications of preference relations and intuitionistic logic. In this paper, a structural characterisation of rough sets induced by quasiorders is given. These rough sets form Nelson algebras defined on algebraic lattices. We prove that any Nelson algebra can be represented as a subalgebra of an algebra defined on rough sets induced by a suitable quasiorder. We also show that Monteiro spaces, rough sets induced by quasiorders …and Nelson algebras defined on T0 -spaces that are Alexandrov topologies can be considered as equivalent structures, because they determine each other up to isomorphism. Show more

DOI: 10.3233/FI-2014-1010

Citation: Fundamenta Informaticae, vol. 131, no. 2, pp. 205-215, 2014

Authors: Marcinkowski, Jerzy | Michaliszyn, Jakub

Article Type: Research Article

Abstract: The Halpern–Shoham logic is a modal logic of time intervals. Some effort has been put in last ten years to classify fragments of this beautiful logic with respect to decidability of its satisfiability problem. We complete this classification by showing — what we believe is quite an unexpected result—that the logic of subintervals, the fragment of the Halpern–Shoham logic where only the operator “during”, or D, is allowed, is undecidable over discrete structures. This is surprising as this, apparently very simple, logic is decidable over dense orders and its reflexive variant is known to be decidable over discrete structures. Our …result subsumes a lot of previous undecidability results of fragments that include D. Show more

Keywords: Halpern–Shoham logic, logic of subintervals, undecidable logic

DOI: 10.3233/FI-2014-1011

Citation: Fundamenta Informaticae, vol. 131, no. 2, pp. 217-240, 2014

Authors: Przytuła, Łukasz

Article Type: Research Article

Abstract: Soccer game is a good playground for testing artificial intelligence of robots and methods for spatial reasoning in real conditions. Decision making and path planning are only two of many tasks performed while playing soccer. This paper describes an application of rough mereology introduced by Polkowski and Skowron (1994) for path planning in robotic soccer game. Our path planning method was based on mereological potential fields introduced by Polkowski and Ośmiałowski (2008) and Ośmiałowski (2009) but was redesigned due to conditions of dynamic soccer environment, so an entirely new method was developed.

Keywords: NAO, Robotics, Soccer, Rough Mereology, Mereological Potential Field, Path Planning

DOI: 10.3233/FI-2014-1012

Citation: Fundamenta Informaticae, vol. 131, no. 2, pp. 241-251, 2014

Authors: Rataj, Artur

Article Type: Research Article

Abstract: We study, on the basis of a simple neural–network like system that we call a spatial network, how several properties of two evolvable systems: a nervous system and computer software, could influence on the evolvability of a genetic algorithm. The following properties are modelled: hierarchical modularity, mirroring, extensive variability and quantitative genetic traits. By mirroring we understand mimicking of the structure of processed data by the structure of the processing algorithm. We estimate the evolvability of several examples of the presented networks, which perform simple image processing tasks, like stereo–to–depth. The evaluation is done by studying the size of these …networks' genotype. Show more

Keywords: nervous system, computer software, genetic algorithm, evolution, hierarchical modularity

DOI: 10.3233/FI-2014-1013

Citation: Fundamenta Informaticae, vol. 131, no. 2, pp. 253-278, 2014