Globally deterministic CD-systems of stateless R-automata with window size 1

Abstract

It is known that cooperating distributed systems (CD-systems) of stateless deterministic restarting automata with window size 1 accept a class of semi-linear languages that properly includes all rational trace languages. Although the component automata of such a CD-system are all deterministic, the CD-system itself is not. Here, we study CD-systems of stateless deterministic restarting automata with window size 1 that are themselves completely deterministic. In fact, we consider two such types of CD-systems: the strictly deterministic systems and the globally deterministic systems.

Keywords:

• restarting automaton
• cooperating distributed system
• determinism
• language class
• rational trace language
• deterministic finite-state acceptor with translucent letters

2010 AMS subject classification:

• 68Q45

Acknowledgements

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. The results of this paper have been presented at the 5th International Conference on Language and Automata Theory and Applications (LATA 2011) in Tarragona, Spain, May 2011. An extended abstract appeared in the proceedings of that conference 14.

Notes

An AFL is an ‘abstract family of languages,’ that is, a class of languages that is closed under certain operations (see, e.g. [19]). Accordingly, an anti-AFL is a class of languages that is not closed under any of the AFL operations.