15 August 2010
Tomorrow I’m leaving for Canada, to attend the 14th International Conference on Developments in Language Theory, held at University of Western Ontario, London. You can find the programme here.
Our DLT 2010 paper, authored by yours truly, Alberto Leporati and Claudio Zandron, is titled On a powerful class of non-universal P systems with active membranes. In it, we describe a restricted variant of P systems with active membranes (computing devices inspired by biological cells) that is not Turing-equivalent, but nonetheless decide a surprisingly large class of languages. This class also seems to be somewhat “new” (we haven’t been able to find any reference to it in the literature).
Consider the operation of tetration (iterated exponentiation), defined as
\[{}^n b = \underbrace{\,b^{b^{b^{\cdot^{\cdot^{\cdot^b}}}}}}_{n \text{ times}}\]and call PTETRA the class of languages decided by Turing machines working in time ${}^{p(n)}2$ for some polynomial p (the P in PTETRA signifies the fact that exponentiation is iterated only polynomially many times instead of, say, exponentially many). This class is trivially closed under union, intersection, complement, and polytime reductions. Furthermore, it’s easy to see that it can also be defined in terms of space ${}^{p(n)}2$ (you can also throw in nondeterminism, if you really want to).
Well, the main result of our paper is the following funny theorem.
Theorem. The class of languages decided by our variant of P system with active membranes is exactly PTETRA.
The proof works like this:
The result is somewhat unexpected, as I was under the impression that all we could do with these P systems was EXPSPACE, and indeed I wasted a few days trying to prove that. Fortunately, reality turned out to be much more interesting.