Department of Computer Science, Faculty of Informatics, University
of Debrecen, 4032
Debrecen, Egyetem tér 1.,
2 Fachbereich Elektrotechnik/Informatik, Universität Kassel, 34109 Kassel, Germany
Accepted: 8 August 2011
We study cooperating distributed systems (CD-systems) of stateless deterministic restarting automata with window size 1 that are equipped with an external pushdown store. In this way we obtain an automata-theoretical characterization for the class of word languages that are linearizations of context-free trace languages.
Mathematics Subject Classification: 68Q45
Key words: Restarting automaton / cooperating distributed system / external pushdown / context-free trace language
The results of this paper have been announced at SOFSEM 2011 in Nový Smokovec, Slovakia, January 2011. An extended abstract appeared in the proceedings of that conference .
This work was supported by grants from the Balassi Intézet Magyar Ösztöndíj Bizottsága (MÖB) and the Deutsche Akademischer Austauschdienst (DAAD). The first author was also supported by the TÁMOP 4.2.1/B-09/1/KONV-2010-0007 project, which is implemented through the New Hungary Development Plan, co-financed by the European Social Fund and the European Regional Development Fund.
© EDP Sciences 2011