The degree of irreversibility in deterministic finite automata

TY - GEN

T1 - The degree of irreversibility in deterministic finite automata

AU - Axelsen, Holger Bock

AU - Holzer, Markus

AU - Kutrib, Martin

N1 - Conference code: 21

PY - 2016

Y1 - 2016

N2 - Recently, Holzer et al. gave a method to decide whether the language accepted by a given deterministic finite automaton (DFA) can also be accepted by some reversible deterministic finite automaton (REV-DFA), and eventually proved NL-completeness. Here, we show that the corresponding problem for nondeterministic finite state 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 languages. 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.

AB - Recently, Holzer et al. gave a method to decide whether the language accepted by a given deterministic finite automaton (DFA) can also be accepted by some reversible deterministic finite automaton (REV-DFA), and eventually proved NL-completeness. Here, we show that the corresponding problem for nondeterministic finite state 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 languages. 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.

UR - http://www.scopus.com/inward/record.url?scp=84978839896&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-40946-7_2

DO - 10.1007/978-3-319-40946-7_2

M3 - Article in proceedings

AN - SCOPUS:84978839896

SN - 978-3-319-40945-0

T3 - Lecture notes in computer science

SP - 15

EP - 26

BT - Implementation and Application of Automata

A2 - Han, Yo-Sub

A2 - Salomaa, Kai

PB - Springer

T2 - 21st International Conference on Implementation and Application of Automata

Y2 - 19 July 2016 through 22 July 2016

ER -