We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
The Degree of Irreversibility in Deterministic Finite Automata.
- Authors
Axelsen, Holger Bock; Holzer, Markus; Kutrib, Martin
- 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.
- Subjects
DETERMINISTIC finite automata; NUMERICAL analysis; FINITE state machines; COMPUTER simulation; SEQUENTIAL machine theory; MATHEMATICAL analysis; PROBABILITY theory
- Publication
International Journal of Foundations of Computer Science, 2017, Vol 28, Issue 5, p503
- ISSN
0129-0541
- Publication type
Article
- DOI
10.1142/S0129054117400044