% This file was created with JabRef 2.5. % Encoding: UTF8 @INPROCEEDINGS{MW2008c, author = {Niall Murphy and Damien Woods}, title = {A characterisation of {NL} using membrane systems without charges and dissolution}, booktitle = {UC}, year = {2008}, pages = {164--176}, publisher = {Springer}, note = {To appear}, abstract = {We apply techniques from complexity theory to a model of biological cellular membranes known as membrane systems or P-systems. Like circuits, membrane systems are defined as uniform families. To date, polynomial time uniformity was the accepted uniformity notion for membrane systems. Here, we introduce the idea of using AC0 and L uniformities and investigate the computational power of membrane systems under these tighter conditions. It turns out that the computational power of some systems is lowered from P to NL, so it seems that our tighter uniformities are more reasonable for these systems. Interestingly, other systems that are known to be lower bounded by P are shown to retain their computational power under the new uniformity conditions. Similarly, a number of membrane systems that are lower bounded by PSPACE retain their power under the new uniformity conditions.}, citeseerurl = {http://www.springerlink.com/content/35qg210662026701}, crossref = {CFFOR2008x}, doi = {http://dx.doi.org/10.1007/978-3-540-85194-3_14}, file = {MW2008c.pdf:MW2008c.pdf:PDF}, owner = {nmurphy}, timestamp = {2008.02.02} } @INPROCEEDINGS{MNWHDDBW2006c, author = {Niall Murphy and Thomas J. Naughton and Damien Woods and Beverley Henley and Kieran McDermott and Elaine Duffy and Peter J. M. van der Burgt and Niamh Woods}, title = {Implementations of a model of physical sorting}, booktitle = {From Utopian to Genuine Unconventional Computers}, year = {2006}, editor = {Andrew Adamatzky and Christof Teuscher}, pages = {79--99}, publisher = {Luniver Press}, abstract = {We define a computational model of physical devices that have a parallel atomic operation that transforms their input, an un-ordered list, in such a way that their output, the sorted list, can be sequentially read off in linear time. We show that several commonly used scientific laboratory techniques (from biology, chemistry, and physics) are instances of the model and we provide experimental implementations.}, file = {MNWHDDBW2006c.pdf:MNWHDDBW2006c.pdf:PDF}, owner = {nmurphy}, timestamp = {2006.07.20} } @ARTICLE{MNWHDDBW2008p, author = {Niall Murphy and Thomas J. Naughton and Damien Woods and Beverley Henley and Kieran McDermott and Elaine Duffy and Peter J. M. van der Burgt and Niamh Woods}, title = {Implementation of a model of physical sorting}, journal = {International Journal of Unconventional Computing}, year = {2008}, volume = {4}, pages = {3--12pp}, number = {8}, 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.}, file = {MNWHDDBW2008p.pdf:MNWHDDBW2008p.pdf:PDF}, keywords = {sorting, natural computation, chromatography, gel electrophoresis, mass spectrometry, optics, physical implementation.}, owner = {nmurphy}, timestamp = {2006.11.20} } @INPROCEEDINGS{MW2007c, author = {Niall Murphy and Damien Woods}, title = {Active membrane systems without charges and using only symmetric elementary division characterise {P}}, booktitle = {Proceedings of the 8th Workshop on Membrane Computing, Thessaloniki, Greece}, year = {2007}, editor = {George Eleftherakis and Petros Kefalas and Gheorghe P{\u a}un}, pages = {455--470}, month = {June}, abstract = {In this paper we introduce a variant of membrane systems with elementary division and without charges. We allow only elementary division where the resulting membranes are identical; we refer to this using the biological term symmetric division. We prove that this model characterises P. This result characterises the power of a class of membrane systems that fall under the so called P conjecture for membrane systems.}, file = {MW2007c.pdf:MW2007c.pdf:PDF}, keywords = {Membrane system, P-system, active membranes, p-conjecture, charges, symmetric division, asymmetric division, elementray divison}, owner = {nmurphy}, timestamp = {2007.09.17} } @INPROCEEDINGS{MW2007p, author = {Niall Murphy and Damien Woods}, title = {Active Membrane Systems Without Charges and Using Only Symmetric Elementary Division Characterise {P}}, booktitle = {Membrane Computing, 8th International Workshop, WMC 2007 Thessaloniki, Greece, June 25-28, 2007 Revised Selected and Invited Papers}, year = {2007}, editor = {G. Eleftherakis and P. Kefalas and G. P{\u a}un and G. Rozenberg and A. Salomaa}, volume = {4860}, series = {LNCS}, pages = {367--384}, publisher = {Springer}, abstract = {In this paper we introduce a variant of membrane systems with elementary division and without charges. We allow only elementary division where the resulting membranes are identical; we refer to this using the biological term symmetric division. We prove that this model characterises P and introduce logspace uniform families. This result characterises the power of a class of membrane systems that fall under the so-called P conjecture for membrane systems.}, doi = {dx.doi.org/10.1007/978-3-540-77312-2_23}, file = {MW2007p.pdf:MW2007p.pdf:PDF}, journal = {Membrane Computing}, owner = {nmurphy}, timestamp = {2008.02.02} } @INPROCEEDINGS{MW2008bc, author = {Murphy, Niall and Woods, Damien}, title = {On acceptance conditions for membrane systems: characterisations of {L} and {NL}}, booktitle = {Complexity of Simple Programs, Proceedings}, year = {2008}, editor = {T. Neary and D. Woods and A.K. Seda and N. Murphy}, pages = {225--242}, month = dec, publisher = {Cork University Press, Cork, Ireland}, isbn = {978-1-906642-00-6}, owner = {nmurphy}, timestamp = {2009.02.02} } @UNPUBLISHED{MW2008mb, author = {Niall Murphy and Damien Woods}, title = {Cells with dividing and dissolving sub-membranes are no more powerful than sequential Turing machines}, note = {In submission to DNA14}, abstract = {Membrane computers with dividing and dissolving membranes are known to solve PSPACE problems in polynomial time. However if division is restricted to membranes that do not contain other membranes, the computational power was so-far unknown. We give a P upper bound on such systems by showing that are simulated by deterministic polynomial time Turing machines. Combined with an earlier result, this gives a P characterisation of these systems. This implies that such systems can not compute, nor be simulated, any faster than in polynomial time.}, owner = {nmurphy}, timestamp = {2008.04.14} } @INPROCEEDINGS{MW2009c, author = {Niall Murphy and Damien Woods}, title = {On acceptance conditions for membrane systems: characterisations of L and NL}, booktitle = {EPTCS: The Complexity of Simple Programs 2008}, year = {2009}, volume = {1}, pages = {172--184}, publisher = {EPTCS}, abstract = {In this paper we investigate the affect of various acceptance conditions on recogniser membrane systems without dissolution. We demonstrate that two particular acceptance conditions (one easier to program, the other easier to prove correctness) both characterise the same complexity class, NL. We also find that by restricting the acceptance conditions we obtain a characterisation of L. We obtain these results by investigating the connectivity properties of dependency graphs that model membrane system computations.}, file = {MW2009c.pdf:MW2009c.pdf:PDF}, owner = {nmurphy}, timestamp = {2009.06.20} } @INPROCEEDINGS{MW2009cb, author = {Niall Murphy and Damien Woods}, title = {The Computational Complexity of Uniformity and Semi-uniformity in Membrane Systems}, booktitle = {Proceedings of the 7th Brainstorming Week on Membrane Computing: Volume 2}, year = {2009}, pages = {73--84}, file = {MW2009cb.pdf:MW2009cb.pdf:PDF}, owner = {nmurphy}, timestamp = {2009.06.20} } @CONFERENCE{MW2009cc, author = {Niall Murphy and Damien Woods}, title = {Uniformity: Uncovering the Frontier of Parallelism}, booktitle = {Proceedings of the 10th Workshop on Membrane Computing, Curtea de Argeş, Romania.}, year = {2009}, pages = {556--560.}, file = {MW2009cc.pdf:MW2009cc.pdf:PDF}, owner = {nmurphy}, timestamp = {2009.08.03} } @TECHREPORT{MW2008m, author = {Niall Murphy and Damien Woods}, title = {A characterisation of {NL} using membrane systems without charges and dissolution}, institution = {Department of Computer Science, National University of Ireland Maynooth, Ireland}, year = {2008}, number = {NUIM-CS-TR-2008-01}, month = jan, abstract = {We apply techniques from complexity theory to a model of biological cellular membranes known as membrane systems or P-systems. Like circuits, membrane systems are defined as uniform families. To date, polynomial time uniformity was the accepted uniformity notion for membrane systems. Here, we introduce the idea of using AC0 and L uniformities and investigate the computational power of membrane systems under these tighter conditions. It turns out that the computational power of some systems is lowered from P to NL, so it seems that our tighter uniformities are more reasonable for these systems. Interestingly, other systems that are known to be lower bounded by P are shown to retain their computational power under the new uniformity conditions. Similarly, a number of membrane systems that are lower bounded by PSPACE retain their power under the new uniformity conditions.}, file = {MW2008m.pdf:MW2008m.pdf:PDF}, owner = {nmurphy}, timestamp = {2008.02.02} } @INPROCEEDINGS{MWN2006c, author = {Niall Murphy and Damien Woods and Thomas J. Naughton}, title = {Bio-Computation using Holliday junctions}, booktitle = {4th International Conference on Information and 4th Irish Conference on the Mathematical Foundations of Computer Science and Information Technology (MFCSIT)}, year = {2006}, pages = {317--320}, address = {Cork, Ireland}, month = {August}, abstract = {We present a design for a novel computing machine composed of an artificial arrangement of DNA and proteins. We characterise the compu- tational power of this construction by proving that its prediction problem is P-Complete.}, file = {MWN2006c.pdf:MWN2006c.pdf:PDF}, keywords = {P-Complete, Holliday junction, biological computer, microtubule.}, owner = {nmurphy}, timestamp = {2007.02.14} } @TECHREPORT{MWN2006m, author = {Niall Murphy and Damien Woods and Thomas J. Naughton}, title = {Stable Sorting Using Special-Purpose Physical Devices}, institution = {Boole Centre for Research in Informatics, University College Cork, Ireland}, year = {2006}, number = {BCRI Preprint 06/2006}, month = {May}, file = {MWN2006m.pdf:MWN2006m.pdf:PDF}, owner = {nmurphy}, timestamp = {2007.02.14} } @TECHREPORT{MWN2005m, author = {Niall Murphy and Damien Woods and Thomas J. Naughton}, title = {On the computational complexity of photosynthesis}, institution = {Department of Computer Science, National University of Ireland Maynooth, Ireland}, year = {2005}, number = {NUIM-CS-TR-2005-03}, month = {September}, file = {MWN2005m.pdf:MWN2005m.pdf:PDF}, owner = {nmurphy}, timestamp = {2007.02.14} } @PROCEEDINGS{CFFOR2008x, title = {Unconventional Computing, 7th International Conference, UC 2008, Vienna, Austria, August 25-28, 2008. Proceedings}, year = {2008}, editor = {Cristian S. Calude and Jos{\'e} F{\'e}lix Costa and Rudolf Freund and Marion Oswald and Grzegorz Rozenberg}, volume = {5204}, series = {Lecture Notes in Computer Science}, publisher = {Springer}, bibsource = {DBLP, http://dblp.uni-trier.de}, booktitle = {UC}, isbn = {978-3-540-85193-6}, owner = {nmurphy}, timestamp = {2008.09.26} }