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:
 Enhance the various types of restarting automata and systems of
restarting automata from devices that recognize (accept) languages
to devices that compute transductions!
 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).
 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 nonexperts in
particular applications much more easily.
However, it is important to guarantee that the considered types of
restarting automata have still sufficient expressive power.
 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.
Mitarbeiter:
Norbert Hundeshagen
Marcel Vollweiler
Veröffentlichungen:

Hundeshagen, N. and Otto, F.:

Restarting transducers, regular languages, and rational relations
Theory of Computing Systems 57 (2015) 195225.

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 MartinVide, C., editors,
Language and Automata Theory and Applications, LATA 2012, Proc.
Lecture Notes in Computer Science 7183, pages 325336,
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 288299,
Springer, Berlin, 2011.

Hundeshagen, N., Otto, F. and Vollweiler, M.:

Transductions computed by PCsystems 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 163172,
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 201222,
World Scientific, Singapore, 2010.