Home

Acceptance conditions for active membranes, characterisations of L and NL

D. Niall Murphy

National University of Ireland, Maynooth


Abstract:
We investigate the effect of various accepting conditions on recogniser
membrane systems without dissolution. We demonstrate that two particular
accepting 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.

  • Date: November 25th 2008, at 17h
  • Place: Seminar room of the Department (ETSII, Module H, First floor)
  • Language: English