Projekt 4 - Cooperating Distributed Systems of Restarting Automata and Generalization of CD Grammar Systems

(Beginn: 01/2009)

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.

Mitarbeiter:

PhD Benedek Nagy
Faculty of Informatics, University of Debrecen

Marcel Vollweiler

Technische Reports:

Nagy, B. and Otto, F.:
On Globally Deterministic CD-Systems of Stateless R-Automata with Window Size One
Kasseler Informatikschriften (KIS) 1/2011, Universität Kassel, March 2011.
Nagy, B. and Otto, F.:
CD-Systems of Stateless Deterministic R(1)-Automata Governed by an External Pushdown Store
Kasseler Informatikschriften (KIS) 4/2010, Universität Kassel, January 2011.
Nagy, B. and Otto, F.:
CD-Systems of Stateless Deterministic R-Automata with Window Size One.
Kasseler Informatikschriften (KIS) 2/2010, Universität Kassel, April 2010.

Veröffentlichungen:

Otto, F.:
On visibly pushdown trace languages
In Italiano, G.F., Margaria-Steffen, T.,Pokorny, J., Quisquater, J.-J., Wattenhofer, R.,editors, SOFSEM 2015, Proc. Lecture Notes in Computer Science 8939, pages 389-400, Springer, Heidelberg, 2015
Nagy, B. and Otto, F.:
Globally deterministic CD-systems of stateless R-automata with window size 1. International Journal of Computer Mathematics 90 (2013) 1254-1277. DOI: 10.1080/00207160.2012.688820.
Nagy, B. and Otto, F.:
Deterministic pushdown CD-systems of stateless deterministic R(1)-automata.
Acta Informatica 50 (2013), 229-255. DOI: 10.1007/s00236-012-0175-x.
Nagy, B. and Otto, F.:
CD-systems of stateless deterministic R-automata with window size one.
Journal of Computer and System Sciences 78 (2012) 780-806
Nagy, B. and Otto, F.:
CD-systems of stateless deterministic R(1)-automata governed by an external pushdown store.
RAIRO Informatique Théorique et Applications 45 (2011) 413-448
Nagy, B. and Otto, F.:
Deterministic pushdown-CD-systems of stateless deterministic R(1)-automata.
In Dömösi, P. and Iván, S.,editors, Automata and Formal Languages, AFL 2011, Proc. pages 328-342, Institute of Mathematics and Informatics, College of Nyiregyhaza, 2011
Otto, F.:
On restarting automata with window size one.
In Holzer, M. and Kutrib, M. and Pighizzini, G.,editors, DCFS 2011, Proc. Lecture Notes in Computer Science 6808, pages 8-33, Springer, Berlin, 2011
Nagy, B., Otto, F., and Vollweiler, M.:
Pushdown automata with translucent pushdown symbols.
In Freund, R. and Holzer, M. and Mereghetti, C. and Otto, F. and Palano, B.,editors, Third Workshop on Non-Classical Models of Automata and Applications (NCMA 2011), Proc. books\@ocg.at, Band 282, pages 193-208, Oesterreichische Computer Gesellschaft.
Nagy, B. and Otto, F.:
Globally deterministic CD-systems of stateless R(1)-automata.
In Dediu, A.H., Inenaga, S. and Martin-Vide, C., editors, Language and Automata Theory and Applications, LATA 2011, Proc. Lecture Notes in Computer Science 6638, pages 390-401, Springer, Berlin, 2011.
Nagy, B. and Otto, F.:
Finite-state acceptors with translucent letters.
In Bel-Enguix, G., Dahl, V. and De La Puente, A.O., editors, BILC 2011: AI Methods for Interdisciplinary Research in Language and Biology, Proc., pages 3--13, SciTePress, Portugal, 2011.
Nagy, B. and Otto, F.:
An automata-theoretical characterization of context-free trace languages.
In Cerná, I., Gyimóthy, T., Hromkovic, J, Jefferey, K., Královic, R., Vukolic;, M. and Wolf, S., editors, SOFSEM 2011: Theory and Practice of Computer Science, Proc. Lecture Notes in Computer Science 6543, pages 406--417, Springer, Berlin, 2011.
Nagy, B. and Otto, F.:
CD-systems of stateless deterministic R(1)-automata accept all rational trace languages.
In Dediu, A.H., Fernau, H. and Martin-Vide, C., editors, Language and Automata Theory and Applications, LATA 2010, Proc. Lecture Notes in Computer Science 6031, pages 463--474, Springer, Berlin, 2010.