A note on the computational complexity of some problems for self-verifying finite automata

Kurzanzeige
dc.contributor.authorHolzer, Markus
dc.contributor.authorJakobi, Sebastian
dc.date.accessioned2022-09-12T09:38:40Z
dc.date.available2017-04-12T13:03:33Z
dc.date.available2022-09-12T09:38:40Z
dc.date.issued2017
dc.description.abstractWe consider the computational complexity of some problems for self-verifying finite automata (svFAs). In particular, we answer a question stated in the open problem session of the Workshop on Descriptional Complexity of Formal Systems 2015 held in Waterloo, Ontario, Canada, on the complexity of the promise version of the general membership problem for svFAs, showing that this problem is NL-complete.en
dc.identifier.urihttp://nbn-resolving.de/urn:nbn:de:hebis:26-opus-126102
dc.identifier.urihttps://jlupub.ub.uni-giessen.de//handle/jlupub/7548
dc.identifier.urihttp://dx.doi.org/10.22029/jlupub-6982
dc.language.isoende_DE
dc.relation.ispartofseriesIFIG Research Report; 1702
dc.rightsIn Copyright*
dc.rights.urihttp://rightsstatements.org/page/InC/1.0/*
dc.subjectself verifying automataen
dc.subjectcomputational complexityen
dc.subjectmembership problemen
dc.subjectemptiness problemen
dc.subjectuniversality problemen
dc.subject.ddcddc:004de_DE
dc.titleA note on the computational complexity of some problems for self-verifying finite automataen
dc.typeworkingPaperde_DE
local.affiliationFB 07 - Mathematik und Informatik, Physik, Geographiede_DE
local.opus.fachgebietInformatikde_DE
local.opus.id12610
local.opus.instituteInstitut für Informatikde_DE

Dateien

Originalbündel
Gerade angezeigt 1 - 1 von 1
Vorschaubild
Name:
Ifig_Report1702.pdf
Größe:
888.68 KB
Format:
Adobe Portable Document Format
Herunterladen

Sammlungen

IFIG Research Report