Fundamenta Informaticae - Volume 127, issue 1-4

Article Type: Other

Abstract: This very special, 27.0 – 1 volume of Fundamenta Informaticae is dedicated to Andrzej Skowron on the occasion of his 70th birthday. The contributions are on an invitational basis, but they have been reviewed according to the usual standards of the journal. The editors want to thank all the contributors and reviewers for their great work. Without it, this volume would be much less special. It is very hard, if even possible, to describe Andrzej Skowron in a finite collection of words. He is such an unique personality and scientist. To get some understanding what he is …like it may help to read the accounts included in this preface. These accounts are provided by persons who interact with Andrzej for years on both professional and personal grounds: Roman Świniarski with family, Janusz Kacprzyk, Damian Niwiński, and Stanisław Matwin. When we started to circulate the idea of this special volume among Andrzej's extended scientific family, we have met an enthusiastic response. So enthusiastic in fact, that we were initially a little bit overwhelmed. Everybody wanted to be on board. We managed to convince several groups of researchers to join forces and write one comprehensive, yet compact article instead of several. In this way, it was possible to fit the material in one, thirty-six-piece volume. The thirty-six articles that make this special volume of Fundamenta Informaticae span over a very wide range of topics. They reflect Andrzej Skowron's activities as a researcher and a scholar as well as his influence on a broad scientific community. In order to make this volume more approachable we have ordered the papers with respect to general areas their represent. To do that we have used a methodology that has quite bit to do with results of one of the research projects Andrzej was recently involved in. Namely, we have manually performed a semantic clustering of our contribution pool. As a result the papers have been organized into four disjoint clusters (thematic groups) that we briefly introduce below. First of the clusters gathers articles that correspond to some fundamental directions in recent and past research of Andrzej Skowron. The reader will find in this cluster papers representing such areas as: foundations of rough sets, logical aspects of both rough and related models of computation, foundational issues relating to logical aspects of non-classical computational systems, formal and computational aspects of inference systems, and nature-inspired computational systems. In this cluster we have contributions by: Mihir K. Chakraborty and Mohua Banerjee; Anna Gomolińska and Marcin Wolski; Ewa Orłowska and Ivo Düntsch; Yiyu Yao; Lech Polkowski and Maria Semeniuk-Polkowska; Ludwik Czaja; Grzegorz Rozenberg, Gheorghe Paun, and Mario J. Perez-Jimenez; Alberto Pettorossi, Fabio Fioravanti, Maurizio Proietti, and Valerio Senni; Andrzej Szałas and Patrick Doherty. The second cluster contains papers that describe research results in topics associated with discovering, representing and making use of knowledge learned form data. In particular, several of approaches described in these papers make use of reducts and decision rules. The contributions made by Andrzej Skowron to methods and algorithms for representation, reduction, and simplification of information retrieved from data are instrumental here. There are also papers that deal with approximations and approximation spaces, an area pioneered by Andrzej. Members of this cluster are papers by: Mikhail Moshkov, Talha Amin, Igor Chikalov, and Beata Zielosko; Roman Słowiński, Salvatore Greco, and Izabela Szczęch; Jerzy Grzymała-Busse and Patrick G. Clark; Wojciech Ziarko and Xugunag Chen; Shusaku Tsumoto and Shoji Hirano; Zbigniew Raś and Hakim Touati; Hui Wang and Ivo Düntsch; Zbigniew Suraj and Krzysztof Pancerz; Jan Komorowski, Marcin Kruczyk, Nicholas Baltzer, Jakub Mieczkowski, Michał Dramiński, and Jacek Koronacki. The third group of contributions relates to another large area of research on which Andrzej Skowron left his mark. The papers represent studies on fundamentals and applications of granular approach to knowledge-based systems as well as investigations into underlying notions of closeness, similarity, and nearness. They also address challenges associated with construction and usage of granular systems – in particular multi-layered, hierarchical ones – in knowledge discovery and decision support. Papers by the following authors make this group: Sankar K. Pal, Jayanta Kumar Pal, and Shubhra Sankar Ray; Marzena Kryszkiewicz; Bożena Kostek and Andrzej Kaczmarek; Alicja Wakulicz-Deja, Agnieszka Nowak-Brzezińska, and Małgorzata Przybyła-Kasperek; James Peters and Sheela Ramanna; Hung Son Nguyen, Sinh Hoa Nguyen, Tuan Trung Nguyen, and Marcin Szczuka; Guoyin Wang, Yuchao Liu, Deyi Li, and Wen He; Witold Pedrycz; Tsau Young Lin, Yong Liu, and Wenliang Huang. The fourth and final group contains nine papers that represent a little wider range of topics. Among them are papers that deal with data processing in general, including research related to database technology as well as search techniques. There are papers in this cluster that deal with data and knowledge representation and navigation. There are also described various aspects of data mining including those that make use of multiagent approach as well as methods based on processing of visual information. In this cluster the reader will find contributions by: Jarosław Stepaniuk, Maciej Kopczyński, and Tomasz Grzes; Dominik Ślęzak, Piotr Synak, Arkadiusz Wojna, and Jakub Wróblewski; Henryk Rybiński and Jacek Lewandowski; Jiming Liu, Hao Lan Zhang, and Yanchun Zhang; Jan G. Bazan, Andrzej Jankowski, and Sylwia Buregwa-Czuma; Wojciech Froelich, Rafał Deja, and Grażyna Deja; Piotr Wasilewski and Adam Krasuski; Ning Zhong, Linchan Qin, Shengfu Lu, and Mi Li; Andrzej Czyżewski and Karol Lisowski. The editors of this special volume would like to wish a Happy Birthday to Andrzej and hope that he will like this little gift. Dominik Ślęzak Hung Son Nguyen Marcin Szczuka October 2013 Show more

DOI: 10.3233/FI-2013-891

Citation: Fundamenta Informaticae, vol. 127, no. 1-4, pp. xix-xxviii, 2013

Authors: Chakraborty, Mihir K. | Banerjee, Mohua

Article Type: Research Article

Abstract: The article analyses prevalent definitions of rough sets from the foundational and mathematical perspectives. In particular, the issue of language dependency in the definitions, and implications of the definitions on the issue of vagueness are discussed in detail.

Keywords: Rough sets, Vagueness

DOI: 10.3233/FI-2013-892

Citation: Fundamenta Informaticae, vol. 127, no. 1-4, pp. 1-15, 2013

Authors: Wolski, Marcin | Gomolińska, Anna

Article Type: Research Article

Abstract: The paper addresses the problem of concept formation (knowledge granulation) in the settings of rough set theory. The original version of rough set theory implicitly accommodates a lot of well-established philosophical assumptions about concept formation as presented by A. Rand. However, as suggested by S. Hawking and L. Mlodinow, one has also to consider the dynamics of the universe of objects and different scales at which concepts may be formed. These both aspects have already been discussed separately in rough set theory. Different forms of dynamics have been addressed explicitly – especially the case of extending the universe by new …objects; in contrast, different scales of description have been addressed implicitly, mainly within the Granular Computing (GrC) paradigm. Following the example of Life, the famous game invented by J. Conway, we describe the corresponding dynamics in Pawlak information systems using a GrC driven methodology. Having dynamics discussed, we address the problem of concept formation at zoom-out scales of description. To this end, we build Scott systems as information systems describing the universe at a coarser scale than the original scale of Pawlak systems. We regard these systems as a special type of classifications, which have already been studied in the context of rough sets by A. Skowron et al. Show more

Keywords: rough set, granular computing, pre-bilattice, classification, Scott system

DOI: 10.3233/FI-2013-893

Citation: Fundamenta Informaticae, vol. 127, no. 1-4, pp. 17-33, 2013

Authors: Düntsch, Ivo | Orłowska, Ewa

Article Type: Research Article

Abstract: Rough relation algebras are a generalization of relation algebras such that the underlying lattice structure is a regular double Stone algebra. Standard models are algebras of rough relations. A discrete duality is a relationship between classes of algebras and classes of relational systems (frames). In this paper we prove a discrete duality for a class of rough relation algebras and a class of frames.

DOI: 10.3233/FI-2013-894

Citation: Fundamenta Informaticae, vol. 127, no. 1-4, pp. 35-47, 2013

Authors: Yao, Yiyu

Article Type: Research Article

Abstract: In rough set theory, one typically considers pairs of dual entities such as a pair of lower and upper approximations, a pair of indiscernibility and discernibility relations, a pair of sets of core and non-useful attributes, and several more. By adopting a framework known as hypercubes of duality, of which the square of opposition is a special case, this paper investigates the role of duality for interpreting fundamental concepts in rough set analysis. The objective is not to introduce new concepts, but to revisit the existing concepts by casting them in a common framework so that we can obtain more …insights into an understanding of these concepts and their relationships. We demonstrate that these concepts can, in fact, be defined and explained in a common framework, although they first appear to be very different and have been studied in somewhat isolated ways. Show more

Keywords: Core attributes, useful and non-useful attributes, duality, hypercubes of duality, indiscernibility and discernibility relations and matrices, lower and upper approximations, square of opposition

DOI: 10.3233/FI-2013-895

Citation: Fundamenta Informaticae, vol. 127, no. 1-4, pp. 49-64, 2013

Authors: Semeniuk-Polkowska, Maria | Polkowski, Lech

Article Type: Research Article

Abstract: The notion of extensionality means in plain sense that properties of complex things can be expressed by means of their simple components, in particular, that two things are identical if and only if certain of their components or features are identical; e.g., the Leibniz Identitas Indiscernibilium Principle: two things are identical if each applicable to them operator yields the same result on either; or, extensionality for sets, viz., two sets are identical if and only if they consist of identical elements. In mereology, this property is expressed by the statement that two things are identical if their parts are the …same. However, building a thing from parts may proceed in various ways and this, unexpectedly, yields various extensionality principles. Also, building a thing may lead to things identical with respect to parts but distinct with respect, e.g., to usage. We address the question of extensionality for artifacts, i.e., things produced in some assembling or creative process in order to satisfy a chosen purpose of usage, and, we formulate the extensionality principle for artifacts which takes into account the assembling process and requires for identity of two artifacts that assembling graphs for the two be isomorphic in a specified sense. In parallel, we consider the design process and design things showing the canonical correspondence between abstracta as design products and concreta as artifacts. In the end, we discuss approximate artifacts as a result of assembling with spare parts which analysis does involve rough mereology. Show more

Keywords: Mereology, Rough Mereology, Artifacts, Extensionality Property

DOI: 10.3233/FI-2013-896

Citation: Fundamenta Informaticae, vol. 127, no. 1-4, pp. 65-80, 2013

Authors: Czaja, Ludwik

Article Type: Research Article

Abstract: Information system of net structures based on their calculus (a distributive lattice) is introduced and, in this context, basic notions of rough set theory are re-formulated and exemplified.

DOI: 10.3233/FI-2013-897

Citation: Fundamenta Informaticae, vol. 127, no. 1-4, pp. 81-97, 2013

Authors: Păun, Gheorghe | Pérez-Jiménez, Mario J. | Rozenberg, Grzegorz

Article Type: Research Article

Abstract: This paper continues an investigation into bridging two research areas concerned with natural computing: membrane computing and reaction systems. More specifically, the paper considers a transfer of two assumptions/axioms of reaction systems, non-permanency and the threshold assumption, into the framework of membrane computing. It is proved that: (1) spiking neural P systems with non-permanency of spikes assumption characterize the semilinear sets of numbers, and (2) symport/antiport P systems with threshold assumption (translated as ω multiplicity of objects) can solve SAT in polynomial time. Also, several open research problems are stated.

Keywords: Membrane computing, reaction system, semilinear set, fypercomputation, SAT

DOI: 10.3233/FI-2013-898

Citation: Fundamenta Informaticae, vol. 127, no. 1-4, pp. 99-114, 2013

Authors: Fioravanti, Fabio | Pettorossi, Alberto | Proietti, Maurizio | Senni, Valerio

Article Type: Research Article

Abstract: In this paper we present an overview of the unfold/fold proof method, a method for proving theorems about programs, based on program transformation. As a metalanguage for specifying programs and program properties we adopt constraint logic programming (CLP), and we present a set of transformation rules (including the familiar unfolding and folding rules) which preserve the semantics of CLP programs. Then, we show how program transformation strategies can be used, similarly to theorem proving tactics, for guiding the application of the transformation rules and inferring the properties to be proved. We work out three examples: (i) the proof of predicate …equivalences, applied to the verification of equality between CCS processes, (ii) the proof of first order formulas via an extension of the quantifier elimination method, and (iii) the proof of temporal properties of infinite state concurrent systems, by using a transformation strategy that performs program specialization. Show more

Keywords: Automated theorem proving, program transformation, constraint logic programming, program specialization, bisimilarity, quantifier elimination, temporal logics

DOI: 10.3233/FI-2013-899

Citation: Fundamenta Informaticae, vol. 127, no. 1-4, pp. 115-134, 2013

Authors: Doherty, Patrick | Szałas, Andrzej

Article Type: Research Article

Abstract: This paper focuses on approximate reasoning based on the use of approximation spaces. Approximation spaces and the approximated relations induced by them are a generalization of the rough set-based approximations of Pawlak. Approximation spaces are used to define neighborhoods around individuals and rough inclusion functions. These in turn are used to define approximate sets and relations. In any of the approaches, one would like to embed such relations in an appropriate logical theory which can be used as a reasoning engine for specific applications with specific constraints. We propose a framework which permits a formal study of the relationship between …properties of approximations and properties of approximation spaces. Using ideas from correspondence theory, we develop an analogous framework for approximation spaces. We also show that this framework can be strongly supported by automated techniques for quantifier elimination. Show more

Keywords: approximate reasoning, rough sets, approximation spaces, quantifier elimination, knowledge representation

DOI: 10.3233/FI-2013-900

Citation: Fundamenta Informaticae, vol. 127, no. 1-4, pp. 135-149, 2013