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

Authors: Polkowski, Lech | Semeniuk–Polkowska, Maria

Article Type: Research Article

Abstract: The notion of a boundary belongs in the canon of the most important notions of mereotopology, the topological theory induced by mereological structures; the importance of this notion rests not only in its applications to practical spatial reasoning, e.g., in geographical information systems, where it is usually couched under the term of a contour and applied in systems related to economy, welfare, climate, wildlife etc., but also in its impact on reasoning schemes elaborated for reasoning about spatial objects, represented as regions, about spatial locutions etc. The difficulty with this notion lies primarily in the fact that boundaries are things …not belonging in mereological universa of things of which they are boundaries. Various authors, from philosophers through mathematicians to logicians and computer scientists proposed schemes for defining and treating boundaries. We propose two approaches to boundaries; the first aims at defining boundaries as things possibly in the universe in question, i.e., composed of existing things, whereas the second defines them as things in a meta–space built over the mereological universe in question, i.e., we assume a priori that boundaries are in a sense ‘things at infinity’, in an agreement with the topological nature of boundaries. Of the two equivalent topological definitions of a boundary, the first, global, defining the boundary as the difference between the closure and the interior of the set, and the second, local, defining it as the set of boundary points whose all neighborhoods transect the set, the first calls for the first type of the boundary and the second is best fitted for the meta–boundary. In the text that follows, we discuss mereology and rough mereology notions (sects. 2, 3), the topological approach to the notion of a boundary and the model ROM with which we illustrate our discussion (sect. 4), the mereology approach (sect. 5), and the approach based on rough mereology and granular computing in the framework of rough mereology (sect. 6). Show more

Keywords: spatial reasoning, mereotopology, boundary, mereology, rough mereology, granular computing

DOI: 10.3233/FI-2014-1074

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

Authors: Redziejowski, Roman R.

Article Type: Research Article

Abstract: Parsing Expression Grammar (PEG) encodes a recursive-descent parser with limited backtracking. The parser has many useful properties. Converting PEG to an executable parser is a rather straightforward task. Unfortunately, PEG is not well understood as a language definition tool. It is thus of a practical interest to construct PEGs for languages specified in some familiar way, such as Backus-Naur Form (BNF). The problem was attacked by Medeiros in an elegant way by noticing that both PEG and BNF can be formally defined in a very similar way. Some of his results were extended in a previous paper by this author. …We continue here with further extensions. Show more

DOI: 10.3233/FI-2014-1075

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

Authors: Schumann, Andrew | Pancerz, Krzysztof

Article Type: Research Article

Abstract: Our research is focused on creation of a new object-oriented programming language for Physarum polycephalum computing. Physarum polycephalum is a one-cell organism that can be used for developing a biological architecture of different abstract devices, among others, the digital ones. In the paper, we use an abstract graphical language in the form of Petri nets to describe the Physarum polycephalum behavior. Petri nets are a good formalism to assist designers and support hardware design tools, especially in developing concurrent systems. At the beginning stage considered in this paper, we show how to build Petri net models, and next implement them …as Physarum polycephalum machines, of basic logic gates AND, OR, NOT, and simple combinational circuits on the example of the 1-to-2 demultiplexer. Show more

DOI: 10.3233/FI-2014-1076

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

Authors: Tran, Thanh-Luong | Ha, Quang-Thuy | Hoang, Thi-Lan-Giao | Nguyen, Linh Anh | Nguyen, Hung Son

Article Type: Research Article

Abstract: Concept learning in description logics (DLs) is similar to binary classification in traditional machine learning. The difference is that in DLs objects are described not only by attributes but also by binary relationships between objects. In this paper, we develop the first bisimulation-based method of concept learning in DLs for the following setting: given a knowledge base KB in a DL, a set of objects standing for positive examples and a set of objects standing for negative examples, learn a concept C in that DL such that the positive examples are instances of C w.r.t. KB, while the negative examples …are not instances of C w.r.t. KB. We also prove soundness of our method and investigate its C-learnability. Show more

DOI: 10.3233/FI-2014-1077

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

Authors: Werner, Matthias | Popova-Zeugmann, Louchka | Haustein, Mario | Pelz, E.

Article Type: Research Article

Abstract: In this paper we investigate Timed Petri nets (TPN) with fixed, possibly zero, durations and maximal step semantics. We define a new state representation where a state is a pair of a marking for the places and a marking for the transitions (a matrix of clocks). For this representation of states we provide an algebraic state equation. Such a state equation lets us prove a sufficient condition for the non-reachability of a state in a TPN. This application of the state equation is subsequently illustrated by an example.

DOI: 10.3233/FI-2014-1078

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