Fundamenta Informaticae - Volume 109, issue 3

Authors: Czaja, Ludwik

Article Type: Other

DOI: 10.3233/FI-2011-506

Citation: Fundamenta Informaticae, vol. 109, no. 3, pp. i-i, 2011

Authors: Bashkin, Vladimir A. | Lomazova, Irina A.

Article Type: Research Article

Abstract: A new formalism of Resource Driven Automata Nets (RDA-nets) is presented. A RDA-net has two levels: a system level is represented by a net of active resources, describing distribution of agents/resources and their interactions; agents in an object level are finite automata, communicating via ports and shared resources of a system level. RDA-nets are assigned for modeling mobility in multi-agent systems from the resource dependence perspective. We prove that RDA-nets have the same expressive power as Petri nets and give examples of modeling agent communications, dynamics and mobility.

Keywords: multi-agent systems, Petri nets, automata, communication, mobility

DOI: 10.3233/FI-2011-507

Citation: Fundamenta Informaticae, vol. 109, no. 3, pp. 223-236, 2011

Authors: Bellia, Marco | Occhiuto, M. Eugenia

Article Type: Research Article

Abstract: In the last years, the Java community has been arguing about adding closures to Java in order to improve expressivity. The debate has not yet terminated but all proposals seem to converge towards a notion of Simple Closures which contain only the essential features of anonymous functions. This paper addresses the problem of defining a rigorous semantics for Simple Closures. The technique adopted is well known and has already been used to prove interesting properties of other extensions of Java. A minimal calculus is defined: Featherweight Java extended with Simple Closures. Syntax and semantics of such a calculus are defined …and type safety, backward compatibility, and the abstraction property are proved. Show more

DOI: 10.3233/FI-2011-508

Citation: Fundamenta Informaticae, vol. 109, no. 3, pp. 237-253, 2011

Authors: Czaja, Ludwik

Article Type: Research Article

Abstract: Phenomena that inherently happen in distributed computing - some types of deadlock and fairness or starvation - are examined in a client-server model. Messages travelling between clients and a server are: request for an action, permission to start it, and termination of its execution. Deadlock-prone and (un)fair behaviours are formulated for the model and equivalence of the respective formulae to formulae expressing emptiness and finiteness of some sets generated by the model is established. From these results, some answers to decision problems for the aforesaid properties are obtained. Furthermore, equivalence between the so-called strong fairness (specified by first-order formula) and …weak-fairness (second-order formula) is demonstrated. Show more

DOI: 10.3233/FI-2011-509

Citation: Fundamenta Informaticae, vol. 109, no. 3, pp. 255-264, 2011

Authors: Gomolińska, Anna

Article Type: Research Article

Abstract: In this article we continue searching for functions which might be used as measures of inclusion of information granules in information granules. Starting with a 3-valued logic having an adequate logical matrix, we show how to derive a corresponding graded inclusion function. We report on the results of examination of several best known 3-valued logics in this respect. We also give some basic properties of the inclusion functions obtained.

Keywords: rough inclusion, rough approximation, Zadeh fuzzy inclusion, 3-valued logics

DOI: 10.3233/FI-2011-510

Citation: Fundamenta Informaticae, vol. 109, no. 3, pp. 265-279, 2011

Authors: Gruska, Damas P.

Article Type: Research Article

Abstract: Formalisms for description how much information on private actions can be obtained by observing public ones are presented. Two sets of private actions are considered. The set of actions which execution is guaranteed according to observations and the set of actions which execution is excluded according to observations. Since information flows could be realized also by means of different covert channels as time, termination and divergence this possibility is considered as well. Both qualitative and quantitative dimensions of the flow are considered.

Keywords: information flow, security, non-interference, termination, divergence, covert channel

DOI: 10.3233/FI-2011-511

Citation: Fundamenta Informaticae, vol. 109, no. 3, pp. 281-295, 2011

Authors: Kudlek, Manfred

Article Type: Research Article

Abstract: Between modal logic and closure operators for topological spaces as well as for formal languages there exists a strong relation. Modal logic allows to define classes of formal languages in several ways.

DOI: 10.3233/FI-2011-512

Citation: Fundamenta Informaticae, vol. 109, no. 3, pp. 297-304, 2011

Authors: Męski, Artur | Penczek, Wojciech | Półrola, Agata

Article Type: Research Article

Abstract: In the paper we present a bounded model checking for 1-safe Petri nets and properties expressed in LTL and the universal fragment of CTL, based on binary decision diagrams. The presented experimental results show that we have obtained a technique which performs better in some of the considered cases, in comparison with the existing SAT-based implementation. The results are also compared with standard BDD-based symbolic method.

DOI: 10.3233/FI-2011-513

Citation: Fundamenta Informaticae, vol. 109, no. 3, pp. 305-321, 2011

Authors: Redziejowski, Roman R.

Article Type: Research Article

Abstract: In an earlier paper, the author adapted to Parsing Expression Grammars (PEGs) the properties FIRST and FOLLOW used in the construction of predictive top-down parsers. The purpose was to obtain warnings for possible “language hiding”. It turned out that FIRST does not work well with lookahead expressions. To repair this, it is replaced here by a property named BITES that is a set of input strings instead of terminals.

DOI: 10.3233/FI-2011-514

Citation: Fundamenta Informaticae, vol. 109, no. 3, pp. 323-337, 2011

Authors: Szczuka, Marcin | Skowron, Andrzej | Stepaniuk, Jarosław

Article Type: Research Article

Abstract: We discuss the problem of measuring the quality of decision support (classification) system that involves granularity based on rough set concepts. We put forward the proposal for such quality measure in the case when the underlying granular system is based on rough sets and makes use of approximation spaces. We introduce the notion of approximation, loss function, and quality measures that are inspired by empirical risk assessment for classifiers in the field of statistical learning. We further discuss the possibilities of improving the quality measure by extrapolating the loss function using function approximation methods originating in extensions of the concept …of approximation space. Show more

Keywords: quality measure, loss function, rough sets, granularity, approximation, neighborhood, empirical risk, classification

DOI: 10.3233/FI-2011-515

Citation: Fundamenta Informaticae, vol. 109, no. 3, pp. 339-354, 2011

Authors: Wolski, Marcin

Article Type: Research Article

Abstract: In the paper we discuss logical approaches to incomplete and/or nondeterministic data. As is well-known, complete and deterministic information systems induce indiscernibility relations and the lower and upper approximations regarded as operators obey the laws of S5 modal system. In the case of incomplete and/or nondeterministic systems, this modal approach yields a few more binary relations on the set of objects (e.g. NIL-structures and NIL-logics). Anyway, in both cases, there are relations which play a dominant role. The main idea of this study is to shift the focus from relations to objects – that is why we use the term …object-directed. Following well-established traditions from modal logics, we would like to consider objects with empty or non-single attribute values as a special kind of worlds. In consequence, in the object-directed approach there would be two sorts of objects and (usually) one relation in contrast to the relation-directed approach where we have one sort of objects and a number of relations. In the first part of our paper we shall discuss a global kind of non-normality and show how rough approximations can be linked to weak modal systems. In the second part we shall consider a local kind of non-normality; this time we use a multi-valued modal system Q introduced by A. N. Prior. The key idea offered by the paper is to regard incomplete and/or nondeterministic information systems as a source of non-normal models for (modal) descriptor languages. Show more

DOI: 10.3233/FI-2011-516

Citation: Fundamenta Informaticae, vol. 109, no. 3, pp. 355-368, 2011