Role Of Theory In Computer Science, The: Essays Dedicated To Janusz Brzozowski

Essays Dedicated to Janusz Brzozowski

Stavros Konstantinidis, Nelma Moreira;Rog????rio Reis;Jeffrey Shallit;

• Publisher: WSPC
• Year: 2017
• eBook ISBN: 9789813148215
• Topic: Computer Science
• Subtopic: Computer Science General
• Index: Computer Science

-->

This volume brings together the work of several prominent researchers who have collaborated with Janusz Brzozowski, or worked in topics he developed, in the areas of regular languages, syntactic semigroups of formal languages, the dot-depth hierarchy, and formal modeling of circuit testing and software specification using automata theory.

-->

Chapter 1

Reaction Systems: A Model of Computation Inspired by the Functioning of the Living Cell

Andrzej Ehrenfeucht

University of Colorado, Department of Computer Science
Boulder CO 80309-0347 USA

Ion Petre

Computational Biomodeling Laboratory
Åbo Akademi University and Turku Centre for Computer Science
Turku 20500, Finland

Grzegorz Rozenberg

Leiden Institute of Advanced Computer Science, Leiden University
Niels Bohrweg 1, 2333 CA Leiden, The Netherlands
and
University of Colorado, Department of Computer Science
Boulder CO 80309-0347 USA

Reaction systems are a model of computation inspired by the functioning of the living cell. They formalize the interactions between biochemical reactions that form the basic mechanism (the skeleton) underlying this functioning. This paper is a tutorial-style introduction to reaction systems – it introduces the basic notions, and reviews a number of research directions which are motivated either by biological considerations, or by the need to understand the basic formal processes (computations) underlying the dynamic behavior of reaction systems.

Contents

1.1.Introduction

1.2.Preliminaries

1.3.Basic Notions

1.4.Power Set Functions

1.5.Relationship to Transition Systems

1.6.Measurement Functions

1.7.Reaction Systems with Duration

1.8.A Reaction Systems Model for the Self-Assembly of Intermediate Filaments

1.9.A Reaction Systems Model for the Heat Shock Response

1.10.Discussion

References

1.1.Introduction

Natural Computing (see, e.g., [27, 37]) is concerned with models of computation, computational techniques, and computing technologies (referred to as human-designed computing) inspired by nature, as well as with investigating, in terms of information processing, phenomena taking place in nature (referred to as computing taking place in nature).

Well-known examples of the former strand of research include evolutionary computation (inspired by Darwinian evolution of species), neural computation (inspired by the functioning of the central nervous system and the brain), artificial immune systems (inspired by the natural immune system), quantum computing (inspired by quantum mechanics), and molecular computing (inspired by molecular biology). Examples of the latter strand include investigations into the computational nature of self-assembly, the computational nature of brain processes, the computational nature of developmental processes, and the computational nature of biochemical reactions.

A research line which has attracted a lot of attention in natural computing is the functioning of the living cell. It is a central research topic for biology and biochemistry, while at the same time it is very attractive for computer science because, for example, it leads to novel models of computation.

This paper belongs to this research line. The methodology underlying the model presented in this paper is to first propose the basic mechanism underlying the functioning of the living cell, and then to attempt (first) to understand this mechanism only. It consists of the interactions between biochemical reactions taking place in the living cell. These interactions form the bare skeleton of the functioning of the living cell. It will still require many additional levels (on top of the skeleton) to achieve a basic understanding of how the living cell functions.

A key property of interactions between biochemical reactions is that they are based on two mechanisms: facilitation and inhibition. The product of one reaction may contain reactants of some reactions (and hence facilitate these reactions) and it may contain inhibitors of some reactions (and hence inhibit these reactions).

The model of reaction systems (introduced in [19]; also see, e.g., [6, 14, 15]) formalizes biochemical reactions in such a way that dynamic processes taking place in reaction systems formalize these interactions. Moreover, because this model is concerned with interactions taking place within the living cell, the formal notion of a dynamic process in reaction systems also captures the interactions with an environment, reflecting the fact that the living cell is an open system.

This paper is a tutorial-style introduction to reaction systems. It introduces basic notions together with the underlying intuition and motivation, and then it presents a number of representative research directions. The paper is organized as follows.

In Section 1.3 we first introduce the basic (formal) notion of a reaction and define its effect on the current state of a (biochemical) system. Each reaction b is of the form b = (R_b, I_b, P_b), where R_b are all reactants b needs to take place, I_b is the set of all inhibitors of b (if any of them is present in the current state T, then b will not take place in T), and P_b is the product set of b (if b takes place in the current state T, then it contributes its product set P_b to the successor state of T). Then we present reaction systems as a model of interactions between biochemical reactions in the ...

Table of contents

• Cover
• Halftitle
• Title
• Copyright
• Dedication
• Preface
• Short Biography for Janusz A. Brzozowski
• Contents
• Chapter 1. Reaction Systems: A Model of Computation Inspired by the Functioning of the Living Cell
• Chapter 2. Solving Fixed Point Equations over Complete Semirings
• Chapter 3. Structure and Complexity of Some Subregular Language Families
• Chapter 4. The Arduous Road to Modelling: Excerpts from Records of an Enjoyable Co-operation of Nearly 20 Years
• Chapter 5. Is Complementation Evil?
• Chapter 6. Quasi-Distances and Weighted Finite Automata
• Chapter 7. Open Problems about Regular Languages, 35 Years Later
• Chapter 8. The Dot-Depth Hierarchy, 45 Years Later
• Chapter 9. Depth of Closed Classes of Truth Functions in Many-valued Logic
• Chapter 10. CSP for Parallelising Brzozowski’s DFA Construction Algorithm
• Chapter 11. Programming Examples of Space-Filling Curves
• Author Index