Fundamenta Informaticae - Volume 133, issue 2-3

Authors: Czaja, Ludwik

Article Type: Other

DOI: 10.3233/FI-2014-1064

Citation: Fundamenta Informaticae, vol. 133, no. 2-3, pp. i-i, 2014

Authors: Bellia, Marco | Occhiuto, M. Eugenia

Article Type: Research Article

Abstract: We investigate the relation between Combinatory Logic and Wang Tiles with the aim of studying Combinators as a programming language for Self-Assembly and DNA computing. We introduce a subset of Combinatory Logic, SKI# , which is Turing Complete, includes simply Typed Combinatory Logic and contains only combinators whose computations require finitely many different redexes. Then, we define a language of Tiles, SKI-Tile, for the representation and the computation of the terms of SKI# in Self-Assembly. Moreover, we introduce a program development methodology that given any computable function, expressed in SKI# , provides a finite set of Tiles that self-assemble …to return the computations of the function applications. Finally, the methodology is applied to the derivation of a SKI-Tile program that self-assemble to compute the factorial function. Show more

DOI: 10.3233/FI-2014-1065

Citation: Fundamenta Informaticae, vol. 133, no. 2-3, pp. 105-121, 2014

Authors: Czaja, Ludwik

Article Type: Research Article

Abstract: A network system is given as a set of Petri net-like structures called agents. Each agent has a singled out place interpreted as a communication port with ingoing edges labelled with send(p1 , ..., pn ) and receive(q1 , ..., qm ) commands, where pi , qj are names of ports of its interlocutors. Every such edge exits a transition emiting a request for send or receive message. A transmission channel between the agent and its intelocutors is established when its port holds a send or receive command, while ports of its interlocutors hold respective (matching) communication commands. This …gives rise to communication between the agent and its interlocutors, after which the channel is disrupted: hence floating channels. Some behavioural properties of such network system are examined, their decision complexity, deadlock and fairness in their number. Show more

DOI: 10.3233/FI-2014-1066

Citation: Fundamenta Informaticae, vol. 133, no. 2-3, pp. 123-132, 2014

Authors: Dubtsov, Roman | Oshevskaya, Elena | Virbitskaite, Irina

Article Type: Research Article

Abstract: The intention of this paper is to introduce a timed extension of transition systems with independence, and to study its categorical interrelations with other time-sensitive models. In particular, we show the existence of a chain of coreflections leading from a category of the model of timed transition systems with independence to a category of a specially defined model of marked Scott domains. As an intermediate semantics we use a timed extension of occurrence transition systems with independence, able to properly capture causality and independence relations which arise in the presence of time delays.

DOI: 10.3233/FI-2014-1067

Citation: Fundamenta Informaticae, vol. 133, no. 2-3, pp. 133-147, 2014

Authors: Gomolińska, Anna | Wolski, Marcin

Article Type: Research Article

Abstract: Rough inclusion functions are mappings considered in rough set theory with which one can measure the degree of inclusion of a set (information granule) in a set (information granule) in line with rough mereology. On the other hand, similarity indices are mappings used in cluster analysis with which one can compare clusterings, and clustering methods with respect to similarity. In this article we show that a large number of similarity indices, known from the literature, can be generated by three simple rough inclusion functions, the standard rough inclusion function included.

Keywords: rough inclusion function, similarity index, cluster analysis, granular computing

DOI: 10.3233/FI-2014-1068

Citation: Fundamenta Informaticae, vol. 133, no. 2-3, pp. 149-163, 2014

Authors: Gruska, Damas P.

Article Type: Research Article

Abstract: Opacity testing is formalized and studied. We specify opacity testers as well as tested systems by (timed) process algebras. We model various testers according to how sophisticated observations of tested system they can make and which kind of conclusions they can obtain. We use this technique to define several realistic security properties. The properties are studied and compared with other security concepts.

Keywords: opacity, process algebras, information flow, security

DOI: 10.3233/FI-2014-1069

Citation: Fundamenta Informaticae, vol. 133, no. 2-3, pp. 165-179, 2014

Authors: Jankowski, Andrzej | Skowron, Andrzej | Swiniarski, Roman W.

Article Type: Research Article

Abstract: Information granules (infogranules, for short) are widely discussed in the literature. In particular, let us mention here the rough granular computing approach based on the rough set approach and its combination with other approaches to soft computing. However, the issues related to interactions of infogranules with the physical world and to perception of interactions in the physical world by infogranules are not well elaborated yet. On the other hand the understanding of interactions is the critical issue of complex systems. We propose to model complex systems by interactive computational systems (ICS) created by societies of agents. Computations in ICS are …based on complex granules (c-granules, for short). In the paper we concentrate on some basic issues related to interactive computations based on c-granules performed by agents in the physical world. Show more

Keywords: granular computing, rough set, interaction, information granule, physical object, complex granule, interactive computational system

DOI: 10.3233/FI-2014-1070

Citation: Fundamenta Informaticae, vol. 133, no. 2-3, pp. 181-196, 2014

Authors: Kalenkova, Anna A. | Lomazova, Irina A.

Article Type: Research Article

Abstract: Process mining is a relatively new field of computer science which deals with process discovery and analysis based on event logs. In this work we consider the problem of discovering workflow nets with cancellation regions from event logs. Cancellations occur in the majority of real-life event logs. In spite of huge amount of process mining techniques little has been done on cancellation regions discovery. We show that the state-based region algorithm gives labeled Petri nets with overcomplicated control flow structure for logs with cancellations. We propose a novel method to discover cancellation regions from the transition systems built on event …logs and show the way to construct equivalent workflow net with reset arcs to simplify the control flow structure. Show more

DOI: 10.3233/FI-2014-1071

Citation: Fundamenta Informaticae, vol. 133, no. 2-3, pp. 197-209, 2014

Authors: Knapik, Michał | Penczek, Wojciech

Article Type: Research Article

Abstract: We show how to synthesise parameter values under which a given property, expressed in a certain extension of CTL, called RTCTLP , holds in a parametric timed Kripke structure. We prove the decidability of parameter synthesis for RTCTLP by showing how to restrict the infinite space of parameter valuations to its finite subset and employ a brute-force algorithm. The brute-force approach soon becomes intractable, therefore we propose a symbolic algorithm for RTCTLP parameter synthesis. Similarly to the fixed-point symbolic model checking approach, we introduce special operators which stabilise on the solution. The process of stabilisation is essentially a …translation from the RTCTLP parameter synthesis problem to a discrete optimization task. We show that the proposed method is sound and complete and provide some complexity results. We argue that this approach leads to new opportunities in model checking, including the use of integer programming and related tools. Show more

DOI: 10.3233/FI-2014-1072

Citation: Fundamenta Informaticae, vol. 133, no. 2-3, pp. 211-226, 2014

Authors: Płaczek, Stanisław | Adhikari, Bijaya

Article Type: Research Article

Abstract: Artificial Neural Networks are of much interest for many practical reasons. As of today, they are widely implemented. Of many possible ANNs, the most widely used one is the back-propagation model with direct connection. In this model the input layer is fed with input data and each subsequent layers are fed with the output of preceding layer. This model can be extended by feeding the input data to each layer. This article argues that this new model, named Cross Forward Connection, is optimal than the widely used Direct Connection.

DOI: 10.3233/FI-2014-1073

Citation: Fundamenta Informaticae, vol. 133, no. 2-3, pp. 227-240, 2014