A note on the computational complexity of some problems for self-verifying finite automata
Loading...
Date
Authors
Advisors/Reviewers
Further Contributors
Contributing Institutions
Publisher
Journal Title
Journal ISSN
Volume Title
Publisher
License
Quotable link
Abstract
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.Link to publications or other datasets
Description
Notes
Original publication in
Original publication in
Anthology
Collections
URI of original publication
Forschungsdaten
Series
IFIG Research Report; 1702