Journal article

Publication year: 2013

Pages: 1083-1097

Journal: International Journal of Foundations of Computer Science

Volume number: 24

Issue number: 7

ISSN: 0129-0541

eISSN: 1793-6373

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

Publisher: World Scientific Publishing

Abstract: 
We introduce E-equivalence, which is a straightforward generalization of almost-equivalence. While almost-equivalence asks for ordinary equivalence up to a finite number of exceptions, in E-equivalence these exceptions or errors must belong to a (regular) set E. The computational complexity of deterministic finite automata (DFAs) minimization problems and their variants w.r.t. almost- and E-equivalence are studied. We show that there is a significant difference in the complexity of problems related to almost-equivalence, and those related to E-equivalence. Moreover, since hyper-minimal and E-minimal automata are not necessarily unique (up to isomorphism as for minimal DFAs), we consider the problem of counting the number of these minimal automata.

Harvard Citation style: Holzer, M. and Jakobi, S. (2013) FROM EQUIVALENCE TO ALMOST-EQUIVALENCE, AND BEYOND: MINIMIZING AUTOMATA WITH ERRORS, International Journal of Foundations of Computer Science, 24(7), pp. 1083-1097. https://doi.org/10.1142/S0129054113400327

APA Citation style: Holzer, M., & Jakobi, S. (2013). FROM EQUIVALENCE TO ALMOST-EQUIVALENCE, AND BEYOND: MINIMIZING AUTOMATA WITH ERRORS. International Journal of Foundations of Computer Science. 24(7), 1083-1097. https://doi.org/10.1142/S0129054113400327