On acceptance conditions for membrane systems: characterisations of L and NL

Niall Murphy
Damien Woods

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.

In Turlough Neary, Damien Woods, Tony Seda and Niall Murphy: Proceedings International Workshop on The Complexity of Simple Programs (CSP 2008), Cork, Ireland, 6-7th December 2008, Electronic Proceedings in Theoretical Computer Science 1, pp. 172–184.
Published: 25th June 2009.

ArXived at: http://dx.doi.org/10.4204/EPTCS.1.17 bibtex PDF

Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org