Project without external funding

Cooperating Distributed Systems

Project Details

Project duration: 01/2009–12/2010

Abstract

The restarting automaton was invented to model the ``analysis by reduction,''

which is a technique from linguistics to analyze sentences of natural

languages with a free word order. In fact, many aspects of the work on

restarting automata are motivated by basic tasks from computational

linguistics. A restarting automaton consists of a finite-state control,

a read/write window of a fixed size k>0, and a flexible tape.

It works in cycles, where in each

cycle it performs a local rewrite operation on the current tape content.

After a finite number of cycles it halts and accepts or rejects.

A ``cooperating distributed (short CD) system'' of restarting

automata is a finite collection of restarting automata that share a

single tape and that cooperate in analyzing a sentence. They use a

protocol to determine which of the automata is active at any given

time. So far CD systems of restarting automata have been studied only

for a few classical modes of operation (protocols). Here it is

intended to carry more recent modes of operation from CD grammar

systems over to CD systems of restarting automata. Among them we

plan to study the ed-mode (which uses explicit enable/disable

conditions) and more generally various types of competence based

modes. Secondly we plan to study generalizations of CD grammar systems,

where a pushdown stack is being used as an auxiliary data structure

to determine the next component to become active. In this way a

runtime stack can be simulated, resulting in a much more involved

control over which component becomes active at any time. Finally,

also further extensions of restarting automata are to be studied.

One option are ``parallel communicating systems'' of restarting automata,

that is, a finite collection of restarting automata that each work on their

own tape, but that can exchange information on request.