Warning: strtotime(): It is not safe to rely on the system's timezone settings. You are *required* to use the date.timezone setting or the date_default_timezone_set() function. In case you used any of those methods and you are still getting this warning, you most likely misspelled the timezone identifier. We selected the timezone 'UTC' for now, but please set date.timezone to select your timezone. in /var/www/html/www_publications/index.php on line 342

Warning: Cannot modify header information - headers already sent by (output started at /var/www/html/www_publications/index.php:342) in /var/www/html/www_publications/index.php on line 4076
Static Sorting P Systems (bibtex)
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},
}
Powered by bibtexbrowser