Projekt 6 - Transductions Computed by Systems of Restarting Automata
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 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.
Transductions computed by restarting automata of simple types will
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.