Static Sorting P Systems (bibtex)
by Alhazov, Artiom and Sburlan, DragoÅŸ
Abstract:
The topic of this chapter is application of P systems for sorting problems, i.e., constructing sorting algorithms for various variants of P systems. Traditional studies of sorting assume a constant time for comparing two numbers and compute the time complexity with respect to the number of components of a vector to be sorted. Here we assume the number of components to be a fixed number k, and study various algorithms with distinct generative features based on different models of P systems, and their time complexity with respect to the maximal number, or to their sum. Massively parallel computations that can be realized within the framework of P systems offer a premise to major improvements of the classical integer sorting problems. Despite this important characteristic we will see that, depending on the model used, the massive parallelism feature cannot be always used, and so, some results will have the complexity â€œcomparableâ€? with the classical integer sorting algorithms. Still, computing an (ordered) word from an (unordered) multiset can be a goal not only for computer science but also, at least, for bio-synthesis (separating mixed objects according to some characteristics). Here, we will pass from ranking algorithms that, starting with numbers represented as multisets, produce symbols in an order, to effective sorting algorithms.
Reference:
Static Sorting P Systems (Alhazov, Artiom and Sburlan, DragoÅŸ), Chapter in (G. Ciobanu, Gh. Paun, M.J. Perez-Jimenez, ed.), Springer-Verlag, 2005.
Bibtex Entry:
@InBook{c96,
pages     = {215-252},
title     = {Static Sorting P Systems},
publisher = {Springer-Verlag},
year      = {2005},
author    = {Alhazov, Artiom AND Sburlan, DragoÅŸ},
editor    = {G. Ciobanu, Gh. Paun, M.J. Perez-Jimenez},
series    = {Natural Computing Series},
abstract  = {The topic of this chapter is application of P systems for sorting problems, i.e., constructing sorting algorithms for various variants of P systems. Traditional studies of sorting assume a constant time for comparing two numbers and compute the time complexity with respect to the number of components of a vector to be sorted. Here we assume the number of components to be a fixed number k, and study various algorithms with distinct generative features based on different models of P systems, and their time complexity with respect to the maximal number, or to their sum. Massively parallel computations that can be realized within the framework of P systems offer a premise to major improvements of the classical integer sorting problems. Despite this important characteristic we will see that, depending on the model used, the massive parallelism feature cannot be always used, and so, some results will have the complexity â€œcomparableâ€? with the classical integer sorting algorithms. Still, computing an (ordered) word from an (unordered) multiset can be a goal not only for computer science but also, at least, for bio-synthesis (separating mixed objects according to some characteristics). Here, we will pass from ranking algorithms that, starting with numbers represented as multisets, produce symbols in an order, to effective sorting algorithms.},
booktitle = {Applications of Membrane Computing},
keywords  = {Static Sorting, Ranking, P Systems},
pdf       = {pdfs/AS2005a.pdf},
}