Wyniki wyszukiwania - BazTech

1

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.

2

Solving a PSPACE-Complete Problem by Recognizing P Systems with Restricted Active Membranes

Alhazov A., Martin-Vide C., Pan L.

Fundamenta Informaticae

|

2003

|

Vol. 58, nr 2

67--77

EN

P systems are parallel molecular computing models based on processing multisets of objects in cell-like membrane structures. Recently, Petr Sosík has shown that a semi-uniform family of P systems with active membranes and 2-division is able to solve the PSPACE-complete problem QBF-SAT in linear time; he has also conjectured that the membrane dissolving rules of the (d) type may be omitted, but probably not the (f) type rules for non-elementary membrane division. In this paper, we partially confirm the conjecture proving that dissolving rules are not necessary. Moreover, the construction is now uniform. It still remains open whether or not non-elementary membrane division is needed.

3

Recursive Calculus with Membranes

Atanasiu A., Martin-Vide C.

Fundamenta Informaticae

|

2002

|

Vol. 49, nr 1-3

45-59

EN

P systems are computing models where certain objects evolve in parallel in a hierarchical membrane structure. Recent results show that this model is a promising framework for solving NP-complete problems in polynomial time. A variant of P systems with active membranes is proposed in this paper. It uses a new operation called ``subordonation", based on the process of ``endocytosis" of membranes: a membrane can be entirely absorbed by another membrane, preserving its content. This class of P systems with active membranes can compute all Turing computable mappings. Arithmetical operations defined in [1] can be obtained as particular cases of primitive recursive functions, but with a higher complexity degree.

4

On the Injectivity of the Parikh Matrix Mapping

Atanasiu A., Martin-Vide C., Mateescu A.

Fundamenta Informaticae

|

2002

|

Vol. 49, nr 4

289-299

EN

In this paper we investigate the injectivity of the Parikh matrix mapping. This research is done mainly on the binary alphabet. We identify a family of binary words, refered to as ``palindromic amiable'', such that two such words are palindromic amiable if and only if they have the same image by the Parikh matrix mapping. Some other related problems are discussed, too.

5

Membrane Systems with Coupled Transport: Universality and Normal Forms

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

Fundamenta Informaticae

|

2002

|

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.

6

Conditional concatenation

Dassow J., Martin-Vide C., Paun G., Rodriguez-Patón A.

Fundamenta Informaticae

|

2000

|

Vol. 44, Nr 4

353-372

EN

Inspired from biochemistry and DNA computing, we introduce several variants of controlled concatenation of strings and languages: a finite set of pairs of strings is given and two arbitrary strings are concatenated only when among their substrings (scattered substrings, of various forms) we can find a pair in this control set. Five types of non-iterated and iterated (like Kleene closure) conditional concatenations are considered. The closure properties of abstract families of languages (hence also of families in the Chomsky hierarchy) are settled. They are similar to the closure properties under usual concatenation and Kleene closure. A representation of regular languages in terms of these operations (and a coding) is also given. Then, we use the new concatenation operations as basic operations in Chomsky grammars: rewriting a nonterminal means concatenating a new string with the strings to the left and the right of that nonterminal, hence restricted concatenations can be used. Context-free grammars working in this restricted manner can generate non-context-free languages; in one case, characterizations of recursively enumerable or of context-sensitive languages are obtained, depending on using or not erasing rules. Some topics for further research are also suggested.

7

On the power of erasing in external contextual grammars

Martin-Vide C., Paun G.

Foundations of Computing and Decision Sciences

|

1998

|

Vol. 23, No. 4

253-260

EN

We prove that extended external contextual grammars with regular choice and with erasing characterize the recursively enumerable languages. This solves an open problem from [3], [2].