Power and Efficiency of Minimal Parallelism in Polarizationless P Systems

Хэвлэлийн нэр: Journal of Automata, Languages and Combinatorics 11 (2006) 3

Зохиогч:  И.Цэрэн-Онолт

Хамтран зохиогч: [И.Цэрэн-Онолт:J.SW42]

Хэвлүүлсэн огноо: 2006-11-11

Хуудас дугаар: 299-320

Өгүүллийн хураангуй:

Minimal parallelism was recently introduced (3) as a way of using the rules of a P system: from each set of applicable rules associated to a membrane, at least one rule must be applied. In this paper, we consider the minimal parallelism for P systems with active membranes without polarizations, using additional features, such as separation operations, changing membrane labels, catalytic or cooperative rules, etc. With several combinations of such features we obtain computational completeness. In cases where membrane division (of elementary or non-elementary membranes) is allowed, we show how SAT can be solved in polynomial time.

Өгүүллийн төрөл: Мэргэжлийн түвшинд хянагддаг сэтгүүл

Өгүүллийн зэрэглэл: Гадаад

Түлхүүр үг: #Minimal parallelism #P systems

Хавсаргасан файл:

Өгүүлэл нэмсэн: И.Цэрэн-Онолт

Монгол Улсын Шинжлэх Ухаан Технологийн Их Сургууль © 2020