Konferenzpaper

Jahr der Veröffentlichung: 2017

Seiten: 503-522

Zeitschrift: International Journal of Foundations of Computer Science

Bandnummer: 28

Heftnummer: 5

ISSN: 0129-0541

eISSN: 1793-6373

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

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

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