On CD-systems of stateless deterministic R-automata with window size one
| dc.date.accessioned | 2010-04-27T06:37:29Z | |
| dc.date.available | 2010-04-27T06:37:29Z | |
| dc.date.issued | 2010-04-27T06:37:29Z | |
| dc.identifier.uri | urn:nbn:de:hebis:34-2010042732682 | |
| dc.identifier.uri | http://hdl.handle.net/123456789/2010042732682 | |
| dc.language.iso | eng | |
| dc.rights | Urheberrechtlich geschützt | |
| dc.rights.uri | https://rightsstatements.org/page/InC/1.0/ | |
| dc.subject | Restarting automaton | eng |
| dc.subject | CD-system | eng |
| dc.subject | stateless device | eng |
| dc.subject | trace language | eng |
| dc.subject | closure property | eng |
| dc.subject.ccs | F.1.1 | |
| dc.subject.ccs | F.4.3 | |
| dc.subject.ddc | 004 | |
| dc.title | On CD-systems of stateless deterministic R-automata with window size one | eng |
| dc.type | Technischer Report | |
| dcterms.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. | eng |
| dcterms.accessRights | open access | |
| dcterms.creator | Nagy, Benedek | |
| dcterms.creator | Otto, Friedrich | |
| dcterms.isPartOf | Kasseler Informatikschriften ;; 2010, 2 | ger |
| dcterms.source.series | Kasseler Informatikschriften | ger |
| dcterms.source.volume | 2010, 2 | ger |