P and dP automata:
unconventional versus classical automata
Erzsebet Csuhaj-Varju


Abstract.
Membrane systems or P systems are computational models abstracted from the architecture and the functioning of the living cell.

P automata are variants of purely communicating (antiport) P systems accepting strings in an automaton-like fashion, combining characteristics of classical automata and natural systems being in interaction with their environment. Strings in the language of a P automaton are obtained as mappings of the multiset sequences which enter the P system through the skin membrane during an accepting computation.

Due to unconventional properties of P automata, new automata-theoretic-like characterizations of well-known language classes were obtained. For example, the context-sensitive language class is the class of languages accepted by P automata working in the so-called maximally parallel manner and using simple, non-erasing mappings for defining words of the language.

Considering distributed P automata (dP automata, for short), i.e., systems consisting of a finite number of component P automata which have their separate inputs and which also may communicate with each other by means of special communication (antiport-like) rules, descriptions of well-known types of classical automata in terms of membrane systems were obtained. For example, it was shown that the way of functioning of any dP automaton having only a finite number of configurations corresponds to that of one-way multitape (multihead) finite automata: the components of the dP automaton represent heads, the multisets entering the components from the environment correspond to the strings scanned by the heads, and the states of the multihead finite automata can be represented by configurations of the dP automaton. Two-way movement can also be interpreted in terms of dP automata, if we consider a so-called double alphabet of objects consisting of barred and non-barred letters with a bijection between the two subalphabets. When a non-barred letter enters a component from the environment, it represents a move to the right of the corresponding head after reading the symbol, if a barred letter enters the system, then a move to the left of the corresponding head is assumed.

In the talk we discuss the correspondence between well-known types of classical automata, as one-way and two-way multihead and multitape finite automata, multi-pushdown automata, linear bounded automata, and the unconventional P and dP automata, pointing out the differences and similarities of the two types of constructs. We also deal with important problems related to classical versus P and dP automata, namely, synchronization, decomposability, reachability, and descriptional complexity.