Implementations of a model of physical sorting

N. Murphy, T.J. Naughton, D. Woods, B. Henley, K. McDermott, E. Duffy, P. J. M. van der Burgt, and N. Woods

International Journal of Unconventional Computing 4(1), 3-12 (2007)

Abstract

We define a model of physical devices that have a parallel atomic operation that transforms an unordered list input such that the sorted output can be sequentially read off in linear time. We show that commonly used biology, chemistry, and physics laboratory techniques are model instances and provide implementations.

Keywords: sorting, natural computation, chromatography, gel electrophoresis, mass spectrometry, optics, physical implementation.

Copyright 2007 Old City Publishing, Inc.

Back to publications: http://www.cs.nuim.ie/~tnaughton/pubs
Home: http://www.cs.nuim.ie/~tnaughton
Contact: