Wyniki wyszukiwania - BazTech

1

P Systems with Insertion and Deletion Exo-Operations

Alhazov A., Krassovitskiy A., Rogozhin Y., Verlan S.

Fundamenta Informaticae

|

2011

|

Vol. 110, nr 1-4

13-28

EN

It is known that insertion-deletion (P) systems with two symbols context-free insertion and deletion rules are not computationally complete. It is thus interesting to consider conditions that would allow such systems to reach computational completeness. In this paper we consider insertion-deletion P systems with insertion and deletion operations applied only at the ends of string (we call them exo-operations). We show that such systems with one-symbol insertion and deletion of up to two symbols are computationally complete, and so are systems with insertion of up to two symbols and one-symbol deletion. The question about the computational power of insertion-deletion P systems with one-symbol insertion and one-symbol deletion operations applied at the ends of string is open. However, the tissue P systems reach computationally completeness even in this case.

2

On Networks of Evolutionary Processors with Nodes of Two Types

Alhazov A., Martin-Vide C., Truthe B., Dassow J., Rogozhin Y.

Fundamenta Informaticae

|

2009

|

Vol. 91, nr 1

1-15

EN

We discuss the power of networks of evolutionary processors where only two types of nodes are allowed. We prove that (up to an intersection with a monoid) every recursively enumerable language can be generated by a network with one deletion and one insertion node. Networks with an arbitrary number of deletion and substitution nodes only produce finite languages, and for each finite language one deletion node or one substitution node is sufficient. Networks with an arbitrary number of insertion and substitution nodes only generate context-sensitive languages, and (up to an intersection with a monoid) every context-sensitive language can be generated by a network with one substitution node and one insertion node. All results are optimal with respect to the number of nodes.

3

Time-Varying Distributed H Systems: An Overview

Margenstern M., Verlan S., Rogozhin Y.

Fundamenta Informaticae

|

2005

|

Vol. 64, nr 1-4

291-306

EN

Time-varying distributed H systems are a well known model of molecular computing. In this article we present an overview of this model, its history, related results, and open problems.

4

Self-describing Turing machines

Margenstern M., Rogozhin Y.

Fundamenta Informaticae

|

2002

|

Vol. 50, nr 3,4

285-303

EN

After a sketchy historical account on the question of self-describeness and self-reproduction, and after discussing the definition of suitable encodings for self-describeness, we give the construction of several self-describing Turing machines, namely self-describing machines with, respectively, 350, 267, 224 and 206 instructions.