Giessener Elektronische Bibliothek

GEB - Giessener Elektronische Bibliothek

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

Holzer, Markus ; Jakobi, Sebastian


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


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

Bookmark bei del.icio.us


Freie Schlagwörter (Englisch): self verifying automata , computational complexity , membership problem , emptiness problem , universality problem
CCS - Klassifikation: F.1.1 Mode , F.1.3 Comp , F.4.3 Form
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 ; 1702
Sprache: Englisch
Erstellungsjahr: 2017
Publikationsdatum: 12.04.2017
Kurzfassung auf Englisch: We 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.
Lizenz: Veröffentlichungsvertrag für Publikationen ohne Print on Demand