Deterministic set automata

dc.contributor.authorKutrib, Martin
dc.contributor.authorMalcher, Andreas
dc.contributor.authorWendlandt, Matthias
dc.date.accessioned2022-09-12T09:38:35Z
dc.date.available2014-09-03T12:41:39Z
dc.date.available2022-09-12T09:38:35Z
dc.date.issued2014
dc.description.abstractWe 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.en
dc.identifier.urihttp://nbn-resolving.de/urn:nbn:de:hebis:26-opus-110573
dc.identifier.urihttps://jlupub.ub.uni-giessen.de//handle/jlupub/7531
dc.identifier.urihttp://dx.doi.org/10.22029/jlupub-6965
dc.language.isoende_DE
dc.relation.ispartofseriesIFIG Research Report; 1402
dc.rightsIn Copyright*
dc.rights.urihttp://rightsstatements.org/page/InC/1.0/*
dc.subjectset automataen
dc.subjectclosure propertiesen
dc.subjectemptiness problemen
dc.subjectdecidabilityen
dc.subject.ddcddc:004de_DE
dc.titleDeterministic set automataen
dc.typeworkingPaperde_DE
local.affiliationFB 07 - Mathematik und Informatik, Physik, Geographiede_DE
local.opus.fachgebietInformatikde_DE
local.opus.id11057
local.opus.instituteInstitut für Informatikde_DE

Dateien

Originalbündel
Gerade angezeigt 1 - 1 von 1
Lade...
Vorschaubild
Name:
Ifig_Report1402.pdf
Größe:
255.57 KB
Format:
Adobe Portable Document Format