Almost all classical types of automata like Turing machines, pushdown automata, stack automata, etc., can be seen as extensions of finite automata, that is, one of their main ingredients is a finite-state control. On the other hand, the so-called P systems introduced by Paun as an unconventional computing model realizing membrane computing are stateless, because it is difficult and even unrealistic to maintain a global state for a massively parallel group of objects appearing in natural phenomena of cell evolution and chemical reactions. Accordingly, it is of interest to study stateless variants of classical models of automata to obtain insight into the real importance of the finite-state control for these devices.
A finite automaton without states (or rather, with a single state only) accepts all words that it can read completely. Thus, the language it accepts is either empty or of the form A*, where A is a subset of the input alphabet. For a stateless pushdown automaton it only makes sense to consider acceptance by empty pushdown. It is well-known that the class of languages that are accepted by stateless pushdown automata coincides with the class CFL of context-free languages. Thus, in this case the resource `pushdown store' can compensate for the loss of states. On the other hand, for deterministic pushdown automata accepting by empty pushdown, the expressive power is known to increase strictly with the number of states. In particular, a language is accepted by a stateless deterministic pushdown automaton if and only if it is a so-called simple language, that is, it is generated by a context-free grammar of a very restricted form. So in this case the resource `pushdown store' cannot compensate for the loss of states.
Recently Ibarra and his co-workers have started the investigation of stateless multihead finite automata and stateless multicounter systems. In particular, they have studied the language accepting power of such devices. Among other results they established infinite strict hierarchies depending on the number of heads. Moreover, they have shown that there is no fixed integer k such that every finite unary language can be accepted by a stateless two-way nondeterministic finite automaton with k heads. Hence, the additional resource `heads' cannot compensate for the loss of states. So, from this point of view, it is a natural and interesting question of how other additional resources given to finite automata relate to the absence or presence of states. Given a particular computational model, are states necessary at all?
In this project we investigate the expressive power of stateless restarting automata. The restarting automaton was introduced by Jancar et al as a formal tool to model the analysis by reduction, which is a technique used in linguistics to analyze sentences of natural languages. Many restricted types of restarting automata have been studied and put into correspondence to more classical types of formal languages. In particular, it has been shown that the classes DCFL, CFL, CRL, and GCSL are all characterized by certain types of restarting automata.
Here we plan to introduce and study the stateless variants of the various types of restarting automata. How is their expressive power related to that of restarting automata of the same type with states? What are the closure properties of the language classes characterized by the various types of stateless restarting automata, and what are the algorithmic properties of these language classes?
Hartmut Messerschmidt
Prof. Dr. Martin Kutrib
Institut für Informatik, Justus-Liebig-Universität Giessen