Repositorio de producción científica de la Universidad de Sevilla

Simulating the Bitonic Sort on a 2D-mesh with P Systems

 

Advanced Search
 
Opened Access Simulating the Bitonic Sort on a 2D-mesh with P Systems
Cites
Show item statistics
Icon
Export to
Author: Ceterchi, Rodica
Pérez Jiménez, Mario de Jesús
Tomescu, Alexandru Ioan
Department: Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial
Date: 2007
Published in: WMC2007: 8th International Workshop on Membrane Computing (2007), p 205-226
ISBN/ISSN: 978-960-89629-2-7
Document type: Presentation
Abstract: This paper gives a version of the parallel bitonic sorting algorithm of Batcher, which can sort N elements in time O(log2 N). When applying it to the 2D mesh architecture, two indexing functions are considered, row-major and shuffled row- major. Some properties are proved for the later, together with a correctness proof of the proposed algorithm. Two simulations with P systems are proposed and discussed. The first one uses dynamic communication graphs and follows the guidelines of the mesh version of the algorithm. The second simulation requires only symbol rewriting rules in one membrane.
Cite: Ceterchi, R., Pérez Jiménez, M.d.J. y Tomescu, A.I. (2007). Simulating the Bitonic Sort on a 2D-mesh with P Systems. En WMC2007: 8th International Workshop on Membrane Computing (205-226), Tesalonica, Grecia: South-East European Research Centre.
Size: 253.5Kb
Format: PDF

URI: http://hdl.handle.net/11441/57262

See editor´s version

This work is under a Creative Commons License: 
Attribution-NonCommercial-NoDerivatives 4.0 Internacional

This item appears in the following Collection(s)