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.
|