KOBRA - Dokumentenserver der Universität Kassel  → Fachbereiche  → FB 16 Elektrotechnik / Informatik  → Kasseler Informatikschriften (KIS)  

Please use this identifier to cite or link to this item: http://nbn-resolving.de/urn:nbn:de:hebis:34-2010042732682

Title: On CD-systems of stateless deterministic R-automata with window size one
Authors: Nagy, BenedekOtto, Friedrich
???metadata.dc.subject.ddc???: 004 - Informatik (Data processing Computer science)
Issue Date: 27-Apr-2010
Series/Report no.: Kasseler Informatikschriften2010, 2
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.
URI: urn:nbn:de:hebis:34-2010042732682
Appears in Collections:Kasseler Informatikschriften (KIS)

Files in This Item:

File Description SizeFormat
Technicalreport2010_2.pdf297.55 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.