Giessener Elektronische Bibliothek

GEB - Giessener Elektronische Bibliothek

Deterministic set automata

Kutrib, Martin ; Malcher, Andreas ; Wendlandt, Matthias


Zum Volltext im pdf-Format: Dokument 1.pdf (256 KB)


Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URN: urn:nbn:de:hebis:26-opus-110573
URL: http://geb.uni-giessen.de/geb/volltexte/2014/11057/

Bookmark bei Connotea Bookmark bei del.icio.us


Freie Schlagwörter (Englisch): set automata , closure properties , emptiness problem , decidability
CCS - Klassifikation: F.4.3 , F.1.1
Universität Justus-Liebig-Universität Gießen
Institut: Institut für Informatik
Fachgebiet: Informatik
DDC-Sachgruppe: Informatik
Dokumentart: ResearchPaper
Zeitschrift, Serie: IFIG Research Report ; 1402 / 2014
Sprache: Englisch
Erstellungsjahr: 2014
Publikationsdatum: 03.09.2014
Kurzfassung auf Englisch: We consider the model of deterministic set automata which are basically deterministic finite automata equipped with a set as an additional storage medium. The basic operations on the set are the insertion of elements, the removing of elements, and the test whether or not an element is in the set. We investigate the computational power of deterministic set automata and compare the language class accepted with the context-free languages and classes of languages accepted by queue automata. As results the incomparability to all classes considered is obtained. In the second part of the paper, we examine the closure properties of the class of DSA languages under Boolean operations. Finally, we show that deterministic set automata may be an interesting model from a practical point of view by proving that their emptiness problem is decidable.
Lizenz: Veröffentlichungsvertrag für Publikationen ohne Print on Demand