Journal article
Authors list: Holzer, Markus; Jakobi, Sebastian
Publication year: 2017
Pages: 229-245
Journal: International Journal of Foundations of Computer Science
Volume number: 28
Issue number: 3
ISSN: 0129-0541
eISSN: 1793-6373
DOI Link: https://doi.org/10.1142/S0129054117500150
Publisher: World Scientific Publishing
Abstract:
We continue our research on minimization problems and related problems for automata w.r.t. to different error profiles, now considering nondeterministic finite automata (NFAs) as inputs. Here the error profiles are almost-equivalence and E-equivalence. We show that the minimization problems and their underlying equivalence problems become PSPACE-complete in most cases. The obtained results nicely fit to the known ones on ordinary NFA minimization, and show a significant difference to the previously obtained results on deterministic finite state machines.
Citation Styles
Harvard Citation style: Holzer, M. and Jakobi, S. (2017) More on Minimizing Finite Automata with Errors - Nondeterministic Machines, International Journal of Foundations of Computer Science, 28(3), pp. 229-245. https://doi.org/10.1142/S0129054117500150
APA Citation style: Holzer, M., & Jakobi, S. (2017). More on Minimizing Finite Automata with Errors - Nondeterministic Machines. International Journal of Foundations of Computer Science. 28(3), 229-245. https://doi.org/10.1142/S0129054117500150
Keywords
almost-equivalence; computational complexity; E-equivalence; EQUIVALENCE; minimal finite automata; nondeterministic finite automata
