Projekt 6 - Transductions Computed by Systems of Restarting Automata

(Beginn: 01/2010)

Restarting automata and certain parallel systems of restarting automata are to be studied that compute transductions (binary relations). The motivation stems from traditional linguistics: how to assign a structure (a sequence of symbols, a dependency tree, or even a more general structure) describing the deep syntax and comprising the meaning of a sentence to a given sentence in a natural language? Here the goals are the following:

  1. Enhance the various types of restarting automata and systems of restarting automata from devices that recognize (accept) languages to devices that compute transductions!
  2. Characterize the classes of transductions that are computed by various types of such devices! In addition, derive closure properties and algorithmic properties for the various classes of transductions obtained in this way! Here those classes of transductions are of particular interest that can be applied in modelling the relationships between the various levels of the formal description of a natural language (like, e.g., the Functional Generative Description (FGD) of the Czech language that is being developed at Prague since the 1960's).
  3. Study simple types of restarting automata! Here types of restarting automata are of particular interest that can be learnt algorithmically from positive (and negative) examples of reduction sequences. Such types of restarting automata could be used by non-experts in particular applications much more easily. However, it is important to guarantee that the considered types of restarting automata have still sufficient expressive power.
  4. Transductions computed by restarting automata of simple types will be studied. Also cooperating distributed systems and parallel communicating systems consisting of several restarting automata of such a simple type will be considered, and the transductions computed by them will be studied.


Norbert Hundeshagen

Marcel Vollweiler


Hundeshagen, N. and Otto, F.:
Restarting transducers, regular languages, and rational relations
Theory of Computing Systems 57 (2015) 195-225.
Hundeshagen N.:
Relations and Transductions realized by Restarting Automata
Dissertation, Fachbereich Elektrotechnik/Informatik, Universität Kassel, 2013.
Hundeshagen, N. and Otto, F.:
Characterizing the rational functions by restarting transducers.
In Dediu, A.-H. and Martin-Vide, C., editors, Language and Automata Theory and Applications, LATA 2012, Proc. Lecture Notes in Computer Science 7183, pages 325-336, Springer, Berlin, 2012.
Hundeshagen, N. and Otto, F.:
Characterizing the regular languages by nonforgetting restarting automata.
In Mauri, G. and Leporati, A., editors, DLT 2011, Proc. Lecture Notes in Computer Science 6795, pages 288-299, Springer, Berlin, 2011.
Hundeshagen, N., Otto, F. and Vollweiler, M.:
Transductions computed by PC-systems of monotone deterministic restarting automata.
In Domaratzki, M. and Salomaa, K., editors, CIAA 2010: Implementation and Application of Automata, Proc. Lecture Notes in Computer Science 6482, pages 163-172, Springer, Berlin, 2011.
Otto, F.:
On proper languages and transformations of lexicalized types of automata.
In Ito, M., Kobayashi, Y. and Shoji, K., editors, Automata, Formal Languages and Algebraic Systems, Proc. of AFLAS 2008, pages 201-222, World Scientific, Singapore, 2010.