Following, we present in this paper various number encodings and operations over multisets. We obtain the most compact encoding and several other interesting
encodings and study their properties using elements of combinatorics over multisets. We
also construct P systems that implement their associated operations. We quantify the effect of adding order to a multiset thus obtaining a string, as going from encoding lengths
of the number n in base b and time complexities of operations of the order b
p
n to lengths
and complexities of order logbn:
(Fénix Editora, 2006) Alhazov, Artiom; Pérez Jiménez, Mario de Jesús; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Ministerio de Educación y Ciencia (MEC). España; Universidad de Sevilla. TIC193: Computación Natural
It is known that the satisfiability problem (SAT) can be solved a semi-
uniform family of deterministic polarizationless P systems with active membranes with
non-elementary membrane division. We present a double improvement of this result by
showing that the satisfiability of a quantified boolean formula (QSAT) can be solved by a
uniform family of P systems of the same kind.
