Project without external funding
Cooperating Distributed Systems of Restarting Automata and Generalizations of CD Grammar 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 finitestate 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 edmode (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.
Publications
2011  Nagy, B., Otto, F., 2011. An automatatheoretical characterization of contextfree trace languages, in: Cerna, I. (Hrsg.), SOFSEM 2011: Theory and Practice of Computer Science, Proc. Springer, Berlin, S. 406–417.  2011   2011   2011  Nagy, B., Otto, F., 2011. Globally deterministic CDsystems of stateless R(1)automata, in: Dediu, A.H. (Hrsg.), Language and Automata Theory and Applications, LATA 2011, Proc. Springer, Berlin, S. 390–401.  2011   2010  Nagy, B., Otto, F., 2010. CDsystems of stateless deterministic R(1)automata accept all rational trace languages, in: Dediu, A.H. (Hrsg.), Language and Automata Theory and Applications, LATA 2010, Proc. Springer, Berlin, S. 463–474.  2010  
