Wyniki wyszukiwania - Biblioteka Nauki

1

Reaction Systems

100%

Ehrenfeucht A. , Rozenberg G.

Fundamenta Informaticae

|

2007

|

tom Vol. 75, nr 1-4

263-280

EN

Interactions between biochemical reactions lie at the heart of functioning of a living cell. In order to formalize these interactions we introduce reaction systems. We motivate them by explicitely stating a number of assumptions/axioms that (we believe) hold for a great number of biochemical reactions - we point out that these assumptions are very different from the ones underlying traditional models of computation. The paper provides the basic definitions, illustrates them by biology and computer science oriented examples, relates reaction systems to some traditional models of computation, and proves some basic properties of reaction systems.

2

Multiset-Based Self-Assembly of Graphs

80%

Bernardini F. , Brijder R. , Rozenberg G. , Zandron C.

Fundamenta Informaticae

|

2007

|

tom Vol. 75, nr 1-4

49-75

EN

We present a model for self-assembly of graphs based on multisets and the formalism of membrane systems. The model deals with aggregates of cells which are defined as undirected graphs where a multiset over a fixed alphabet is assigned to each vertex. The evolution of these aggregates is determined by an application of multiset-based aggregation rules to enlarge the current structure as well as an application of membrane-systems-based communication rules to enable cells to exchange objects alongside the edges of the graph. We compare the generative power of self-assembly membrane systems with and without communication rules, and we characterise properties of the sets of graphs generated by these systems. We also introduce two notions of stability for self-assembly processes that capture the idea of having produced a stable structure. Finally, we investigate self-assembly membrane systems where the alphabet is a singleton.

3

Membrane computing with external output

80%

Paun G. , Rozenberg G. , Salomaa A.

Fundamenta Informaticae

|

2000

|

tom Vol. 41, Nr 3

313-340

EN

A membrane computing system (also called P system) consists of computing cells which are organized hierarchically by the inclusion relation: cells may include cells, which again may include cells, etc. Each cell is enclosed by its membrane. Each cell is an independent computing agent with its own computing program, which produces objects. The interaction between cells consists of the exchange of objects through membranes. The output of a computation is a partially ordered set of objects which leave the system through its external membrane. The fundamental properties of computations in such P systems with external output are investigated. These include the computing power, normal forms, and basic decision problems.

4

Arto Salomaa : publications by Arto Salomaa

80%

Karhumäki J. , Mateescu A. , Rozenberg G.

Fundamenta Informaticae

|

1999

|

tom Vol. 38, Nr 1,2

11-11

5

Bridging Membrane and Reaction Systems : Further Results and Research Topics

80%

Păun G. , Pérez-Jiménez M. J. , Rozenberg G.

Fundamenta Informaticae

|

2013

|

tom Vol. 127, nr 1-4

99--114

EN

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.

6

The Embedding Problem for Switching Classes of Graphs

80%

Ehrenfeucht A. , Hage J. , Harju T. , Rozenberg G.

Fundamenta Informaticae

|

2006

|

tom Vol. 74, nr 1

115-134

EN

In the context of graph transformation we look at the operation of switching, which can be viewed as a method for realizing global transformations of (group-labelled) graphs through local transformations of the vertices. In case vertices are given an identity, various relatively efficient algorithms exist for deciding whether a graph can be switched so that it contains some other graph, the query graph, as an induced subgraph. However, when considering graphs up to isomorphism, we immediately run into the graph isomorphism problem for which no efficient solution is known. Surprisingly enough however, in some cases the decision process can be simplified by transforming the query graph into a ``smaller'' graph without changing the answer. The main lesson learned is that the size of the query graph is not the dominating factor, but its cycle rank. Although a number of our results hold specifically for undirected, unlabelled graphs, we propose a more general framework and give many positive and negative results for more general cases, where the graphs are labelled with elements of a (finitely generated abelian) group.

7

Membrane Systems with Coupled Transport: Universality and Normal Forms

80%

Martin-Vide C. , Paun A. , Paun G. , Rozenberg G.

Fundamenta Informaticae

|

2002

|

tom Vol. 49, nr 1-3

1-15

EN

This paper continues research on membrane systems which function by communication only, meaning that there are no evolving rules for molecules. The whole computation process relies on passage of molecules through membranes - this provides communication between regions of the membrane system. Next to transport of single molecules through membranes (uniport) we also study a coupled transport of molecules, with two molecules passing either in the same direction (symport) or in opposite directions (antiport). We study the computational power of such membrane systems and prove that using only symport one gets Turing universality. Moreover, we prove that five membranes suffice to get Turing universality, and the number of membranes can be decreased to three if forbidding context conditions for transport are used.

8

Model Checking Temporal Properties of Reaction Systems

80%

Męski A. , Penczek W. , Rozenberg G.

Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk

|

2014

|

tom Nr 1028

1--28

EN

This paper defines a temporal logic for reaction systems (RSTL). The logic is interpreted over the models for the context restricted reaction systems that generalize standard reaction systems by controlling context sequences. Moreover, a translation from the context restricted reaction systems into boolean functions is defined in order to be used for a symbolic model checking for RSTL over these systems. Finally, model checking for RSTL is proved to be PSPACE-complete.

PL

Praca wprowadza logikę temporalną dla systemów reakcyjnych (RSTL), która jest interpretowana w modelach dla systemów reakcyjnych z ograniczeniami kontekstów. Systemy te uogólniają standardowe systemy reakcyjne przez wprowadzenie ograniczeń kontrolujących dopuszczalne konteksty. Ponadto, przedstawiono translację z systemów reakcyjnych z ograniczeniami kontekstów do formuł boolowskich, która umożliwia symboliczną weryfikację modelową dla tych systemów oraz RSTL. Wykazano również, że problem weryfikacji modelowej dla RSTL jest problemem PSPACE-zupełnym.

9

Interpreted Trajectories

80%

Domaratzki M. , Rozenberg G. , Salomaa K.

Fundamenta Informaticae

|

2006

|

tom Vol. 73, nr 1-2

81-97

EN

We introduce generalized trajectories where the individual symbols are interpreted as operations performed on the operand words. The various previously considered trajectory-based operations can all be expressed in this formalism. It is shown that the generalized operations can simulate Turing machine computations. We consider the equivalence problem and a notion of unambiguity that is sufficient to make equivalence decidable for regular sets of trajectories under nonincreasing interpretations.