Fundamenta Informaticae - Volume 154, issue 1-4

Authors: Męski, Artur | Koutny, Maciej | Penczek, Wojciech

Article Type: Research Article

Abstract: Reaction systems are a formal model for computational processes inspired by the functioning of the living cell. This paper introduces reaction systems with discrete concentrations, which are an extension of reaction systems allowing for quantitative modelling. We demonstrate that although reaction systems with discrete concentrations are semantically equivalent to the original qualitative reaction systems, they provide much more succinct representations in terms of the number of entities being used. We define a variant of Linear Time Temporal Logic interpreted over models of reaction systems with discrete concentrations. We provide its suitable encoding in SMT, together with bounded model checking, and …present experimental results demonstrating the scalability of the verification method for reaction systems with discrete concentrations. Show more

Keywords: reaction systems, bounded model checking, linear time temporal logic

DOI: 10.3233/FI-2017-1567

Citation: Fundamenta Informaticae, vol. 154, no. 1-4, pp. 289-306, 2017

Authors: Nobile, Marco S. | Porreca, Antonio E. | Spolaor, Simone | Manzoni, Luca | Cazzaniga, Paolo | Mauri, Giancarlo | Besozzi, Daniela

Article Type: Research Article

Abstract: Reaction systems represent a theoretical framework based on the regulation mechanisms of facilitation and inhibition of biochemical reactions. The dynamic process defined by a reaction system is typically derived by hand, starting from the set of reactions and a given context sequence. However, this procedure may be error-prone and time-consuming, especially when the size of the reaction system increases. Here we present HERESY, a simulator of reaction systems accelerated on Graphics Processing Units (GPUs). HERESY is based on a fine-grained parallelization strategy, whereby all reactions are simultaneously executed on the GPU, therefore reducing the overall running time of the simulation. …HERESY is particularly advantageous for the simulation of large-scale reaction systems, consisting of hundreds or thousands of reactions. By considering as test case some reaction systems with an increasing number of reactions and entities, as well as an increasing number of entities per reaction, we show that HERESY allows up to 29× speed-up with respect to a CPU-based simulator of reaction systems. Finally, we provide some directions for the optimization of HERESY, considering minimal reaction systems in normal form. Show more

Keywords: reaction systems, general-purpose GPU computing, high-performance computing, simulation

DOI: 10.3233/FI-2017-1568

Citation: Fundamenta Informaticae, vol. 154, no. 1-4, pp. 307-321, 2017

Authors: Okubo, Fumiya | Yokomori, Takashi

Article Type: Research Article

Abstract: New morphic characterizations in the form of a noted Chomsky-Schützenberger theorem are established for the classes of regular languages, of context-free languages and of languages accepted by chemical reaction automata. Our results include the following: (i) Each λ-free regular language R can be expressed as R = h (Tk ∩ FR ) for some 2-star language FR , an extended 2-star language Tk and a weak coding h . (ii) Each λ-free context-free language L can be expressed as L = h (Dn ∩ FL …) for some 2-local language FL and a projection h . (iii) A language L is accepted by a chemical reaction automaton iff there exist a 2-local language FL and a weak coding h such that L = h (Bn ∩ FL ), where Dn and Bn are a Dyck set and a partially balanced language defined over the n -letter alphabet, respectively. These characterizations improve or shed new light on the previous results. Show more

Keywords: Regular languages, Context-free languages, Chemical reaction automata, Morphic characterizations, Star languages, Local languages

DOI: 10.3233/FI-2017-1569

Citation: Fundamenta Informaticae, vol. 154, no. 1-4, pp. 323-341, 2017

Authors: Polkowski, Lech T.

Article Type: Research Article

Abstract: This work is dedicated to Profesor Andrzej Ehrenfeucht, the eleve of the Warsaw School of Logic and Mathematics on the occasion of His 85th Birthday. We propose to exploit certain of the milestone ideas created by this School and to apply them to data analysis in the framework of the rough set theory proposed by Professor Zdzisław Pawlak. To wit, we apply the idea of fractional truth states due to Jan Łukasiewicz, mereology created by Stanisław Leśniewski and the betweenness relation used by Alfred Tarski as one of primitive predicates in His axiomatization of Euclidean geometry. These ideas applied in …problems of approximate reasoning permit us to formalize calculus of granules of knowledge and use it in preprocessing of data before applying a classification algorithm. Introduction of a mereological version of betweenness relation to data allows for partitioning of data into the kernel and the residuum, both sub-data sets providing a faithful representation of the whole data set and reducing the size of data without any essential loss of accuracy of classification. In the process of algorithmic construction of the partition of data into the kernel and the residuum, we exploit the Dual Indiscernibility Matrix which further allows us to introduce notions of a pair classifier and, more generally, k -classifier yet to be studied. Show more

Keywords: truth values, mereology, betweenness relation, rough sets, shuffled simplices, dual indiscernibility matrix, kernel, residuum, pair classifier

DOI: 10.3233/FI-2017-1570

Citation: Fundamenta Informaticae, vol. 154, no. 1-4, pp. 343-358, 2017

Authors: Rogers, Trent A. | Seki, Shinnosuke

Article Type: Research Article

Abstract: RNA sequences start folding immediately as they are synthesized by RNA polymerase (cotranscriptional folding). The oritatami system (OS) is a novel mathematical model to study computational aspects of cotranscriptional folding. In this paper, we first provide a survey throughout existing research topics and results on oritatami systems and offer research directions of significance. Simulation of an oritatami system in a different ratio (delay) of transcription speed to the speed of folding is one of them. We will introduce a simple notion of simulation, and prove that there is an OS of delay δ that cannot be simulated by any …oritatami system at larger delay. Show more

Keywords: Oritatami system, RNA cotranscriptional folding, Molecular self-assembly, Turing universality, Simulation

DOI: 10.3233/FI-2017-1571

Citation: Fundamenta Informaticae, vol. 154, no. 1-4, pp. 359-372, 2017

Authors: Valencia-Cabrera, Luis | Orellana-Martín, David | Martínez-del-Amor, Miguel A. | Riscos-Núñez, Agustín | Pérez-Jiménez, Mario J.

Article Type: Research Article

Abstract: Membrane computing is a computing paradigm providing a class of distributed parallel computing devices of a biochemical type whose process units represent biological membranes. In the cell-like basic model, a hierarchical membrane structure formally described by a rooted tree is considered. It is well known that families of such systems where the number of membranes can only decrease during a computation (for instance by dissolving membranes), can only solve in polynomial time problems in class P . P systems with active membranes is a variant where membranes play a central role in their dynamics. In the seminal version, membranes …have an electrical polarization (positive, negative, or neutral) associated in any instant, and besides being dissolved, they can also replicate by using division rules. These systems are computationally universal, that is, equivalent in power to deterministic Turing machines, and computationally efficient, that is, able to solve computationally hard problems in polynomial time. If polarizations in membranes are removed and dissolution rules are forbidden, then only problems in class P can be solved in polynomial time by these systems (even in the case when division rules for non-elementary membranes are permitted). In that framework it has been shown that by considering minimal cooperation (left-hand side of such rules consists of at most two symbols) and minimal production (only one object is produced by the application of such rules) in object evolution rules, such systems provide efficient solutions to NP -complete problems. In this paper, minimal cooperation and minimal production in communication rules instead of object evolution rules is studied, and the computational efficiency of these systems is obtained in the case where division rules for non-elementary membranes are permitted. Show more

Keywords: Membrane Computing, polarizationless P systems with active membranes, cooperative rules, the P versus NP problem, SAT problem

DOI: 10.3233/FI-2017-1572

Citation: Fundamenta Informaticae, vol. 154, no. 1-4, pp. 373-385, 2017

Article Type: Other

Citation: Fundamenta Informaticae, vol. 154, no. 1-4, pp. 387-388, 2017