Technischer Report
On CD-systems of stateless deterministic R-automata with window size one
Abstract
We study cooperating distributed systems (CD-systems) of restarting
automata that are very restricted: they are deterministic, they cannot
rewrite, but only delete symbols, they restart immediately after
performing a delete operation, they are stateless, and they have
a read/write window of size 1 only, that is, these are stateless
deterministic R(1)-automata. We study the expressive power of these
systems by relating the class of languages that they accept by mode
=1 computations to other well-studied language classes, showing in
particular that this class only contains semi-linear languages, and
that it includes all rational trace languages. In addition, we
investigate the closure and non-closure properties of this class
of languages and some of its algorithmic properties.
automata that are very restricted: they are deterministic, they cannot
rewrite, but only delete symbols, they restart immediately after
performing a delete operation, they are stateless, and they have
a read/write window of size 1 only, that is, these are stateless
deterministic R(1)-automata. We study the expressive power of these
systems by relating the class of languages that they accept by mode
=1 computations to other well-studied language classes, showing in
particular that this class only contains semi-linear languages, and
that it includes all rational trace languages. In addition, we
investigate the closure and non-closure properties of this class
of languages and some of its algorithmic properties.