Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Fundamenta Informaticae

2 2014

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: rewriting systems

Sortuj według:

Ogranicz wyniki do:

Describing Membrane Computations with a Chemical Calculus

Battyányi P., Vaszil G.

Fundamenta Informaticae

2014

Vol. 134, nr 1/2

39--50

Membrane systems are nature motivated computational models inspired by certain basic features of biological cells and their membranes. They are examples of the chemical computational paradigm which describes computation in terms of chemical solutions where molecules interact according to rules defining their reaction capabilities. Chemical models can be presented by rewriting systems based on multiset manipulations, and they are usually given as a kind of chemical calculus which might also allow non-deterministic and non-sequential computations. Here we study membrane systems from the point of view of the chemical computing paradigm and show how computations of membrane systems can be described by such a chemical calculus.

Constant-Space P Systems with Active Membranes

Leporati A., Manzoni L., Mauri G., Porreca A. E., Zandron C.

Fundamenta Informaticae

2014

Vol. 134, nr 1/2

111--128

We show that a constant amount of space is sufficient to simulate a polynomial-space bounded Turing machine by P systems with active membranes. We thus obtain a new characterisation of PSPACE, which raises interesting questions about the definition of space complexity for P systems. We then propose an alternative definition, where the size of the alphabet and the number of membrane labels of each P system are also taken into account. Finally we prove that, when less than a logarithmic number of membrane labels is available, moving the input objects around the membrane structure without rewriting them is not enough to even distinguish inputs of the same length.