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

Titel: On CD-systems of stateless deterministic R-automata with window size one
Autor(en): Nagy, BenedekOtto, Friedrich
Klassifikation (DDC): 004 - Informatik (Data processing Computer science)
Issue Date: 27-Apr-2010
Serie/Report Nr.: Kasseler Informatikschriften2010, 2
Zusammenfassung: 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.