Journalartikel

Jahr der Veröffentlichung: 2017

Seiten: 229-245

Zeitschrift: International Journal of Foundations of Computer Science

Bandnummer: 28

Heftnummer: 3

ISSN: 0129-0541

eISSN: 1793-6373

DOI Link: https://doi.org/10.1142/S0129054117500150

Verlag: 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.

Harvard-Zitierstil: 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-Zitierstil: 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