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.
Citation
@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},
year={2010}
}
0500 Oax 0501 Text $btxt$2rdacontent 0502 Computermedien $bc$2rdacarrier 1100 2010$n2010 1500 1/eng 2050 ##0##urn:nbn:de:hebis:34-2010042732682 3000 Nagy, Benedek 3010 Otto, Friedrich 4000 On CD-systems of stateless deterministic R-automata with window size one / Nagy, Benedek 4030 4060 Online-Ressource 4085 ##0##=u http://nbn-resolving.de/urn:nbn:de:hebis:34-2010042732682=x R 4204 \$dTechnischer Report 4170 Kasseler Informatikschriften ;; 2010, 2 7136 ##0##urn:nbn:de:hebis:34-2010042732682
<resource xsi:schemaLocation="http://datacite.org/schema/kernel-2.2 http://schema.datacite.org/meta/kernel-2.2/metadata.xsd"> 2010-04-27T06:37:29Z 2010-04-27T06:37:29Z 2010-04-27T06:37:29Z urn:nbn:de:hebis:34-2010042732682 http://hdl.handle.net/123456789/2010042732682 eng Urheberrechtlich geschützt https://rightsstatements.org/page/InC/1.0/ Restarting automaton CD-system stateless device trace language closure property 004 On CD-systems of stateless deterministic R-automata with window size one Technischer Report 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. open access Nagy, Benedek Otto, Friedrich Kasseler Informatikschriften ;; 2010, 2 F.1.1 F.4.3 Kasseler Informatikschriften 2010, 2 </resource>
The following license files are associated with this item:
:Urheberrechtlich geschützt