Wyniki wyszukiwania - BazTech

1

Computational Efficiency of Minimal Cooperation and Distribution in Polarizationless P Systems with Active Membranes

Valencia-Cabrera L., Orellana-Martín D., Martínez-del-Amor M. A., Riscos-Núñez A., Pérez-Jiménez M. J.

Fundamenta Informaticae

|

2017

|

Vol. 153, nr 1/2

147--172

EN

Polarizationless P systems with active membranes are non-cooperative systems, that is, the left-hand side of their rules have a single object. Usually, these systems make use of division rules as a mechanism to produce an exponential workspace in linear time. Division rules are inspired by cell division, a process of nuclear division that occurs when a parent cell divides to produce two identical daughter cells. On the other hand, separation rules are inspired by the membrane fission process, a mechanism by which a biological membrane is split into two new ones in such a manner that the contents of the initial membrane is distributed between the new membranes. In this paper, separation rules are used instead of division rules. The computational efficiency of these models is studied and the role of the (minimal) cooperation in object evolution rules is explored from a computational complexity point of view.

2

The Complexity of Szilard Languages of Matrix Grammars Revisited

Cojocaru L., Mäkinen E.

Fundamenta Informaticae

|

2013

|

Vol. 123, nr 4

381--399

EN

The regulated rewriting mechanism is one of the most efficient methods to augment the Chomsky hierarchy with a large variety of language classes. In this paper we investigate the derivation mechanism in regulated rewriting grammars such as matrix grammars, by studying their Szilard languages. We focus on the complexity of Szilard languages associated with unrestricted and leftmost-like derivations in matrix grammars, with or without appearance checking. The reason is twofold. First, to relate these classes of languages to parallel complexity classes such as NC1 and AC1, and, second, to improve some previous results. We prove that unrestricted Szilard languages and certain leftmost Szilard languages of context-free matrix grammars, without appearance checking, can be accepted by indexing alternating Turing machines in logarithmic time and space. Consequently, these classes are included in UE-uniform NC1. Unrestricted Szilard languages of matrix grammars with appearance checking can be accepted by deterministic Turing machines in O(n log n) time and O(log n) space. Leftmost-like Szilard languages of context-free matrix grammars, with appearance checking, can be recognized by nondeterministic Turing machines by using the same time and space resources. Hence, all these classes are included in AC1.

3

N-axioms Parallel Unification

Bellia M., Occhiuto M.E.

Fundamenta Informaticae

|

2003

|

Vol. 55, nr 2

115-128

EN

MGUmon and MGUk-rep have a complementary role in unification in the complexity class NC . MGUmon is the upper bound of the unification classes that fall in NC and whose inputs admit an unrestricted number of repeated variables. MGUk-rep is the upper bound of the unification classes that still fall in NC but whose inputs admit an unrestricted arity on term constructors. No LogSpace reduction of the one to the other class is known. Moreover, very fast algorithms that solve the two separately are well known but no one is able to compute with both in polylog PRAM-Time. N-axioms unification extends the structure of unification inputs and brings out the notion of interleaving variable as a special repeated variable which serializes independet computations. Based on it, we define the unification class AMGUkp/h whose inputs have a fixed number of interleaving variables but admit unrestricted number of repeated variables and, at the same time, unrestricted arity for term constructors. Constructively, we prove that AMGUkp/h is in NC by introducing a new unification algorithm that works on graph contractions and solves AMGUkp/hin a polylog PRAM time of the input size. Finally, we prove that MGUmon, MGUk-rep and MGUlinear all are LogSpace reducible to AMGUkp/h. Hence, AMGUkp/h becomes the upper bound of the unification classes that are proved to be in NC .