Projekt 2 - Zustandslose Restart-Automaten (Stateless Restarting Automata)

(Beginn: 01/2008)

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?

Mitarbeiter:

Kent Kwee

Hartmut Messerschmidt

Prof. Dr. Martin Kutrib
Institut für Informatik, Justus-Liebig-Universität Giessen

Preprints:

Kwee, K. and Otto, F.:
On some decision problems for stateless deterministic ordered restarting automata.
February 2015.

Veröffentlichungen:

Kwee K. and Otto, F.:
On ordered RRWW-automata
In Brlek S. and Reutenauer C., editors, DLT 2016, Proc., Lecture Notes in Computer Science 9840, 268-279, Springer, Heidelberg, 2016.
Kwee K. and Otto, F.:
On the effects of nondeterminism on ordered restarting automata
In Freivalds R.M., Engels, G. and Catania B., editors, SOFSEM 2016, Proc., Lecture Notes in Computer Science 9587, 369-380, Springer, Heidelberg, 2016.
Kwee K. and Otto, F.:
Deterministic ordered restarting automata that compute functions
In Potapov I., editor, DLT 2015, Proc., Lecture Notes in Computer Science 9168, 401-412, Springer, Heidelberg, 2015.
Wendlandt, M., Kwee K. and Otto, F.:
Reversible ordered restarting automata
In Krivine, J. and Stefani, J.B., editors, RC 2015, Proc., Lecture Notes in Computer Science 9138, 60-75, Springer, Heidelberg, 2015.
Kwee K. and Otto, F.:
On some decision problems for stateless deterministic ordered restarting automata
In Shallit J. and Okhutin A., editors, DCFS 2015, Proceedings , Lecture Notes in Computer Science 9118, 165-176, Springer, Heidelberg, 2015.
Otto, F.:
On the descriptional complexity of deterministic ordered restarting automata
In Jürgensen, H. and Karhumäki, J. and Okhotin, A., editors, DCFS 2014, Proceedings , Lecture Notes in Computer Science 8614, 318-329, Springer, Heidelberg, 2014.
Kutrib, M. and Otto, F.:
On the descriptional complexity of the window size for deleting restarting automata
International Journal of Foundations of Computer Science 24 (2013) 831-846.
Kutrib, M. and Otto, F.:
On CD-Systems of stateless deterministic two-phase RR(1)-automata.
In Bordihn, H., Kutrib, M. and Truthe, B., editors, Languages Alive, Essays Dedicated to Jürgen Dassow on the Occasion of His 65th Birthday, Lecture Notes in Computer Science 7300, pages 111-137, Springer, Berlin, 2012.
Kutrib, M. and Otto, F.:
On the descriptional complexity of the window size for deterministic restarting automata.
In Moreira, N. and Reis, R., editors, CIAA 2012, Proc., Lecture Notes in Computer Science 7381, pages 253-264, Springer, Berlin, 2012.
Kutrib, M., Messerschmidt, H. and Otto, F.:
On stateless deterministic restarting automata.
Acta Informatica 47 (2010) 391-412.
Kutrib, M., Messerschmidt, H. and Otto, F.:
On stateless two-pushdown automata and restarting automata.
Int. Journal of Foundations of Computer Science 21 (2010) 781-798.
Kutrib, M., Messerschmidt, H. and Otto, F.:
On stateless deterministic restarting automata.
In Nielsen, M., Kucera, A., Miltersen, P.B., Palamidessi, C., Tuma, P. and Valencia, F., editors, SOFSEM 2009: Theory and Practice of Computer Science, Proc., Lecture Notes in Computer Science 5404, pages 353-364, Springer, Berlin, 2009.
Kutrib, M., Messerschmidt, H. and Otto, F.:
On stateless two-pushdown automata and restarting automata.
In Csuhaj-Varjú, E. and Ésik, Z., editors, Automata and Formal Languages, AFL 2008, Proc., pages 257-268, Computer and Automation Research Institute, Hungarian Academy of Sciences, 2008.