Fundamenta Informaticae - Volume 133, issue 2-3

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