P automata revisited (Q714827)

The paper continues the study of the variants of membrane systems (P systems) called P automata. These are symport/antiport P systems working in the accepting mode: they accept sequences of (multisets of) objects entering the system during halting computations. Accepted sequences can be mapped to accepted strings in several ways, here the authors consider the so called non-extended variants with permutation as input mapping, that is, the accepted strings are made of the sequence of objects entering the system during an accepting computation (with the assumption that if several objects enter in the same computational step, then the strings with any permutations of them as substrings are considered to be accepted by the system). The paper starts with an overview of previous results on P automata and distributed P automata, mainly from [\textit{R. Freund}, et al., An. Univ. Bucuresti, Mat.-Inform. 58, 5--22 (2009; Zbl 1265.68076)] and from [the authors, Theor. Comput. Sci. 431, 4--12 (2012; Zbl 1279.68095)]. Then a representation theorem for recursively enumerable languages with P automata is presented: For every language \(L\), there is a context-sensitive language \(L'\) which is the same as \(L\) up to a prefix (over a different alphabet) added to the strings of \(L\). (A similar theorem was already known for dP automata, but not for the non-distributed variants.) This theorem is followed by some non-closure results on P automata languages, and then a new model called `P automata with an internal memory' is introduced. One of the membranes of a P automaton with internal memory is a special memory membrane with rules which are ``paired'' with the rules of the skin membrane, in a way that such pairs of rules can only be executed simultaneously. This allows the control of the input flow of objects (from the environment into the system) by the computation going on in the memory membrane. P automata with internal memory are also shown to be more powerful than ``ordinary'' P automata, but the language class they characterize is still strictly included in the class of context-sensitive languages. The last section of the paper contains topic proposals for further research.