Project without external funding

Transductions Computed by Systems of Restarting Automata

Project Details

Project duration: 01/2010–12/2013

Abstract

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 practical 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.