Fundamenta Informaticae - Volume 75, issue 1-4

Article Type: Other

Citation: Fundamenta Informaticae, vol. 75, no. 1-4, pp. vii-viii, 2007

Authors: Peters, J.F. | , A. | Skowron,

Article Type: Other

Citation: Fundamenta Informaticae, vol. 75, no. 1-4, pp. ix-x, 2007

Authors: Balbiani, Philippe | , Dimiter | Vakarelov,

Article Type: Research Article

Abstract: We dedicate this paper to the memory of Zdislaw Pawlak, the founder of rough sets methodology in computer science. A great deal of our scientific work was motivated and influenced by Pawlak's ideas.

Keywords: Information systems, Information relations, Information logics

Citation: Fundamenta Informaticae, vol. 75, no. 1-4, pp. 1-25, 2007

Authors: Bazan, Jan G. | Kruczek, Piotr | Bazan-Socha, Stanislawa | Skowron, Andrzej | Pietrzyk, Jacek J.

Article Type: Research Article

Abstract: The problem considered is how to model perception and identify behavioral patterns of objects changing over time in complex dynamical systems. An approach to solving this problem has been found in the context of rough set theory and methods. Rough set theory introduced by Zdzis?aw Pawlak during the early 1980s provides the foundation for the construction of classifiers, relative to what are known as temporal pattern tables. Temporal patterns can be treated as features that make …it possible to approximate complex concepts. This article introduces some rough set tools for perception modeling that are developed for a system for modeling networks of classifiers. Such networks make it possible to identify behavioral patterns of objects changing over time. They are constructed using an ontology of concepts delivered by experts that engage in approximate reasoning about concepts embedded in such an ontology. We also present a method that we call a method for on-line elimination of non-relevant parts (ENP). This method was developed for on-line elimination of complex object parts that are irrelevant for identifying a given behavioral pattern. The article includes results of experiments that have been performed on data from a vehicular traffic simulator and on medical data obtained from Neonatal Intensive Care Unit in the Department of Pediatrics, Collegium Medicum, Jagiellonian University. The contribution of this article is the introduction of a network of classifiers that make it possible to identify the behavioral patterns of objects that change over time. Show more

Keywords: behavioral pattern, rough sets, concept approximation, complex dynamical system, respiratory failure

Citation: Fundamenta Informaticae, vol. 75, no. 1-4, pp. 27-47, 2007

Authors: Bernardini, Francesco | Brijder, Robert | Rozenberg, Grzegorz | Zandron, Claudio

Article Type: Research Article

Abstract: We present a model for self-assembly of graphs based on multisets and the formalism of membrane systems. The model deals with aggregates of cells which are defined as undirected graphs where a multiset over a fixed alphabet is assigned to each vertex. The evolution of these aggregates is determined by an application of multiset-based aggregation rules to enlarge the current structure as well as an application of membrane-systems-based communication rules to enable cells to exchange objects …alongside the edges of the graph. We compare the generative power of selfassembly membrane systems with and without communication rules, and we characterise properties of the sets of graphs generated by these systems. We also introduce two notions of stability for self-assembly processes that capture the idea of having produced a stable structure. Finally, we investigate self-assembly membrane systems where the alphabet is a singleton. Show more

Keywords: Multisets, Membrane Systems, Self-Assembly, Graph Generation

Citation: Fundamenta Informaticae, vol. 75, no. 1-4, pp. 49-75, 2007

Authors: Bianucci, Daniela | Cattaneo, Gianpiero | Ciucci, Davide

Article Type: Research Article

Abstract: Different generalizations to the case of coverings of the standard approach to entropy applied to partitions of a finite universe X are explored. In the first approach any covering is represented by an identity resolution of fuzzy sets on X and a corresponding probability distribution with associated entropy is defined. A second approach is based on a probability distribution generated by the covering normalizing the standard counting measure. Finally, the extension to a generic covering of …the Liang–Xu approach to entropy is investigated, both from the "global" and the "local" point of view. For each of these three possible entropies the complementary entropy (or co–entropy) is defined showing in particular that the Liang–Xu entropy is a co–entropy. Show more

Citation: Fundamenta Informaticae, vol. 75, no. 1-4, pp. 77-105, 2007

Authors: Buszkowski, Wojciech

Article Type: Research Article

Abstract: We apply basic notions of the theory of rough sets, due to Pawlak [30, 31], to explicate certain properties of unification-based learning algorithms for categorial grammars, introduced in [6, 11] and further developed in e.g. [18, 19, 24, 25, 26, 9, 28, 14, 15, 3]. The outcomes of these algorithms can be used to compute both the lower and the upper approximation of the searched language with respect to the given, finite sample. We show that …these methods are also appropriate for other kinds of formal grammars, e.g. context-free grammars and context-sensitive grammars. Show more

Citation: Fundamenta Informaticae, vol. 75, no. 1-4, pp. 107-121, 2007

Authors: Chakraborty, Mihir K. | Banerjee, Mohua

Article Type: Research Article

Abstract: A dialogue is an 'activity' by a pair of agents to arrive at some kind of understanding over a concept/belief/piece of information etc. represented by a subset (the extension) in some universe of discourse. The universe is partitioned into two different sets of granules (equivalence classes) representing the perceptions of the agents. So, there are two approximation spaces at the beginning. A third approximation space arises out of superimposition of the two partitions. A dialogue is …a finite process of gradual enhancement of the two base subsets of the agents, in their 'common' approximation space. Through this process, various kinds of overlap may emerge between the two final subsets. A first introduction of the idea of a dialogue in rough context was made in [6]. This paper further develops the notion and focusses upon the study of the above-mentioned overlaps in a systematic manner. Given two sets A and B in an approximation space, there are nine possible inclusion relations among the sets lo(A),A, up(A), lo(B),B and up(B) where lo and up denote the lower and upper approximation operators respectively. There are five resulting equivalence classes and the quotient set forms a lattice by implication ordering. That is, of the nine relations, only five are independent and they form an implication or entailment lattice. Starting with this basic lattice other implication lattices are formed. Relationship of these lattices with the various overlap conditions between the final pair of sets arrived at after a dialogue is studied. Finally, examples are given, one of which relates dialogues in rough context with rough belief revision [3] – in a line similar to the approach of [5]. Show more

Keywords: Rough sets, Negotiation, Modal system S5, Belief change

Citation: Fundamenta Informaticae, vol. 75, no. 1-4, pp. 123-139, 2007

Authors: Chen, Haiming | Freund, Rudolf | Ionescu, Mihai | Păun, Gheorghe | Pérez-Jiménez, Mario J.

Article Type: Research Article

Abstract: We continue the study of spiking neural P systems by considering these computing devices as binary string generators: the set of spike trains of halting computations of a given system constitutes the language generated by that system. Although the "direct" generative capacity of spiking neural P systems is rather restricted (some very simple languages cannot be generated in this framework), regular languages are inverse-morphic images of languages of finite spiking neural P systems, and recursively enumerable …languages are projections of inverse-morphic images of languages generated by spiking neural P systems. Show more

Keywords: Membrane computing, spiking neural P systems, Chomsky hierarchy

Citation: Fundamenta Informaticae, vol. 75, no. 1-4, pp. 141-162, 2007

Authors: Demri, Stéphane | , Ewa | Orłowska,

Article Type: Research Article

Abstract: We define a relative version of the logic NIL introduced by Orłowska, Pawlak and Vakarelov and we show that its satisfiability is not only decidable but also EXPTIME-complete. Such a logic combines two ingredients that are seldom present simultaneously in information logics: frame conditions involving more than one information relation and relative frames. The EXPTIME upper bound is obtained by designing a well-suited decision procedure based on the nonemptiness problem of Büchi automata on infinite …trees. The paper provides evidence that Büchi automata on infinite trees are crucial language acceptors even for relative information logics with multiple types of relations. Show more

Keywords: information logic, relative frame, computational complexity, Büchi tree automaton

Citation: Fundamenta Informaticae, vol. 75, no. 1-4, pp. 163-178, 2007