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

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

2009-06-18

arxiv.org/abs/0906.3327v1

EPTCS 1, 2009, pp. 172-184

Computer Science

Computational Complexity

Scientific paper

10.4204/EPTCS.1.17

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.

Affiliated with

Also associated with

No associations

Rating

On acceptance conditions for membrane systems: characterisations of L and NL does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On acceptance conditions for membrane systems: characterisations of L and NL, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On acceptance conditions for membrane systems: characterisations of L and NL will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-725372