Fundamenta Informaticae - Volume 65, issue 3

Authors: Doberkat, Ernst-Erich

Article Type: Research Article

Abstract: We investigate similarities between non-deterministic and probabilistic ways of describing a system in terms of computation trees. We show that the construction of traces for both kinds of relations follows the same principles of construction. Representations of measurable trees in terms of probabilistic relations are given. This shows that stochastic relations may serve as refinements of their non-deterministic counterparts. A convexity argument formalizes the observation that non-deterministic system descriptions are underspecified when …compared to probabilistic ones. The mathematical tools come essentially from the theory of measurable selections. Show more

Keywords: Probabilistic relations, specification techniques (nondeterministic, stochastic), representation theory

Citation: Fundamenta Informaticae, vol. 65, no. 3, pp. 193-209, 2005

Authors: Ehrig, Hartmut

Article Type: Research Article

Abstract: Processes for high-level nets are often defined as processes of the low-level net Flat(n) which is obtained from N via the well-known flattening construction. This low-level notion of processes for high-level nets, however, is not really adequate, because the high-level structure is completely lost. For this reason we have introduced in a previous paper a new notion of high-level net processes for high-level nets which captures the high-level structure. The key notion is a high-level occurrence …net K, which generalizes the well-known notion of occurrence nets from low-level to high-level nets. In contrast to the low-level case we consider high-level occurrence nets together with a set of initial markings of the input places. In this paper we show under which conditions the behavior of low-level occurrence nets and processes can be generalized to the high-level case. A key notion is the instantiation L of a high-level occurrence net K, where L is a low-level subnet of the flattening Flat(K) with isomorphic net structures of L and K. One of our main results characterizes under which conditions a high-level occurrence net - and hence a high-level net process - has unique and nonoverlapping instantiations and can be represented by the union of all its instantiations. Show more

Citation: Fundamenta Informaticae, vol. 65, no. 3, pp. 211-247, 2005

Authors: Mani, A.

Article Type: Research Article

Abstract: In this research a new algebraic semantics of rough set theory including additional meta aspects is proposed. The semantics is based on enhancing the standard rough set theory with notions of 'relative ability of subsets of approximation spaces to approximate'. The eventual algebraic semantics is developed via many deep results in convexity in ordered structures. A new variation of rough set theory, namely 'ill-posed rough set theory' in which it may suffice to know some of …the approximations of sets, is eventually introduced. Show more

Keywords: Rough Algebra, Super Rough Algebra, Rough Logics, Coapproximability, Algebraic Semantics of Rough Logics, Ill-Posed Rough Set Theory

Citation: Fundamenta Informaticae, vol. 65, no. 3, pp. 249-261, 2005

Authors: Mycka, Jerzy

Article Type: Research Article

Abstract: Recursive functions over the reals [6] have been considered, first as a model of analog computation, and second to obtain analog characterizations of classical computational complexity classes [2]. However, one of the operators introduced in the seminal paper by Cris Moore (in 1996), the minimalization operator, creates some difficulties: (a) although differential recursion (the analog counterpart of classical recurrence) is, to some extent, directly implementable in the General Purpose Analog Computer of Claude Shannon, …analog minimalization is far from physical realizability, and (b) analog minimalization was borrowed from classical recursion theory and does not fit well the analytic realm of analog computation. In this paper we use the most natural operator captured from Analysis - the operator of taking a limit - instead of the minimalization with respect to the equivalance of these operators given in [8]. In this context the natural question about coincidence between real recursive functions and Baire classes arises. To solve this problem the limit hierarchy of real recursive funcions is introduced. Relations between Baire classes, effective Baire classes and the limit hierachy are also studied. Show more

Keywords: theory of computation, real recursive functions, hierarchy of real functions

Citation: Fundamenta Informaticae, vol. 65, no. 3, pp. 263-278, 2005

Authors: Verlan, Sergey | Margenstern, Maurice

Article Type: Research Article

Abstract: In this article we consider splicing P systems with one membrane. We show that the original definition of splicing P systems is not complete and we propose several variants in order to complete it. We show that the choice of the variant is important and that the computational power of splicing P systems with one membrane directly depends on it.

Keywords: Membrane computing, Splicing systems, Formal languages, Universal computations

Citation: Fundamenta Informaticae, vol. 65, no. 3, pp. 279-290, 2005