{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:36:57Z","timestamp":1759639017192},"reference-count":5,"publisher":"World Scientific Pub Co Pte Lt","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2017,8]]},"abstract":"<jats:p> 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. <\/jats:p>","DOI":"10.1142\/s0129054117400044","type":"journal-article","created":{"date-parts":[[2017,12,15]],"date-time":"2017-12-15T08:31:43Z","timestamp":1513326703000},"page":"503-522","source":"Crossref","is-referenced-by-count":3,"title":["The Degree of Irreversibility in Deterministic Finite Automata"],"prefix":"10.1142","volume":"28","author":[{"given":"Holger Bock","family":"Axelsen","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Copenhagen, Universitetsparken 5, Copenhagen, Denmark"}]},{"given":"Markus","family":"Holzer","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Informatik, Universit\u00e4t Giessen, Arndtstrasse\u00a02, 35392 Giessen, Germany"}]},{"given":"Martin","family":"Kutrib","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Informatik, Universit\u00e4t Giessen, Arndtstrasse\u00a02, 35392 Giessen, Germany"}]}],"member":"219","published-online":{"date-parts":[[2017,12,15]]},"reference":[{"key":"S0129054117400044BIB002","doi-asserted-by":"publisher","DOI":"10.1070\/RM1961v016n05ABEH004112"},{"key":"S0129054117400044BIB003","volume-title":"Introduction to Formal Language Theory","author":"Harrison M. A.","year":"1978"},{"key":"S0129054117400044BIB007","doi-asserted-by":"publisher","DOI":"10.1147\/rd.53.0183"},{"key":"S0129054117400044BIB009","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.01.041"},{"key":"S0129054117400044BIB011","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)00011-F"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054117400044","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T16:20:22Z","timestamp":1565194822000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054117400044"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8]]},"references-count":5,"journal-issue":{"issue":"05","published-online":{"date-parts":[[2017,12,15]]},"published-print":{"date-parts":[[2017,8]]}},"alternative-id":["10.1142\/S0129054117400044"],"URL":"https:\/\/doi.org\/10.1142\/s0129054117400044","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,8]]}}}