Conference paper

Publication year: 2017

Pages: 503-522

Journal: International Journal of Foundations of Computer Science

Volume number: 28

Issue number: 5

ISSN: 0129-0541

eISSN: 1793-6373

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

Conference: 21st International Conference on Implementation and Application of Automata (CIAA)

Publisher: World Scientific Publishing

Abstract: 
Recently, a method to decide the NL-complete problem of whether the language accepted by a given deterministic finite automaton (DFA) can also be accepted by some reversible deterministic finite automaton (REV-DFA) has been derived. Here, we show that the corresponding problem for nondeterministic finite automata (NFA) is PSPACE-complete. The recent DFA method essentially works by minimizing the DFA and inspecting it for a forbidden pattern. We here study the degree of irreversibility for a regular language, the minimal number of such forbidden patterns necessary in any DFA accepting the language, and show that the degree induces a strict infinite hierarchy of language families. We examine how the degree of irreversibility behaves under the usual language operations union, intersection, complement, concatenation, and Kleene star, showing tight bounds (some asymptotically) on the degree.

Harvard Citation style: Axelsen, H., Holzer, M. and Kutrib, M. (2017) The Degree of Irreversibility in Deterministic Finite Automata, International Journal of Foundations of Computer Science, 28(5), pp. 503-522. https://doi.org/10.1142/S0129054117400044

APA Citation style: Axelsen, H., Holzer, M., & Kutrib, M. (2017). The Degree of Irreversibility in Deterministic Finite Automata. International Journal of Foundations of Computer Science. 28(5), 503-522. https://doi.org/10.1142/S0129054117400044