Holzer, MarkusMarkusHolzerJakobi, SebastianSebastianJakobi2022-09-122017-04-122022-09-122017http://nbn-resolving.de/urn:nbn:de:hebis:26-opus-126102https://jlupub.ub.uni-giessen.de/handle/jlupub/7548http://dx.doi.org/10.22029/jlupub-6982We 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.enIn Copyrightself verifying automatacomputational complexitymembership problememptiness problemuniversality problemddc:004