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.
@techreport{urn:nbn:de:hebis:34-2010042732682,
author ={Nagy, Benedek and Otto, Friedrich},
title ={On CD-systems of stateless deterministic R-automata with window size one},
copyright ={https://rightsstatements.org/page/InC/1.0/},
language ={en},
year ={2010-04-27T06:37:29Z}
}