Conference paper

Publication year: 2018

Pages: 251-270

Journal: International Journal of Foundations of Computer Science

Volume number: 29

Issue number: 2

ISSN: 0129-0541

eISSN: 1793-6373

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

Conference: 19th International Conference on Developments in Language Theory (DLT)

Publisher: World Scientific Publishing

Abstract: 
We study reversible deterministic finite automata (REV-DFAs), that are partial deterministic finite automata whose transition function induces an injective mapping on the state set for every letter of the input alphabet. We give a structural characterization of regular languages that can be accepted by REV-DFAs. This characterization is based on the absence of a forbidden pattern in the (minimal) deterministic state graph. Again with a forbidden pattern approach, we also show that the minimality of REV-DFAs among all equivalent REV-DFAs can be decided. Both forbidden pattern characterizations give rise to NL-complete decision algorithms. In fact, our techniques allow us to construct the minimal REV-DFA for a given minimal DFA. These considerations lead to asymptotic upper and lower bounds on the conversion from DFAs to REV-DFAs. Thus, almost all problems that concern uniqueness and the size of minimal REV-DFAs are solved.

Harvard Citation style: Holzer, M., Jakobi, S. and Kutrib, M. (2018) Minimal Reversible Deterministic Finite Automata, International Journal of Foundations of Computer Science, 29(2), pp. 251-270. https://doi.org/10.1142/S0129054118400063

APA Citation style: Holzer, M., Jakobi, S., & Kutrib, M. (2018). Minimal Reversible Deterministic Finite Automata. International Journal of Foundations of Computer Science. 29(2), 251-270. https://doi.org/10.1142/S0129054118400063