{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,5,19]],"date-time":"2022-05-19T03:11:43Z","timestamp":1652929903577},"reference-count":15,"publisher":"World Scientific Pub Co Pte Ltd","issue":"03n04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2022,4]]},"abstract":"<jats:p> Finite automata whose computations can be reversed, at any point, by knowing the last [Formula: see text] symbols read from the input, for a fixed [Formula: see text], are considered. These devices and their accepted languages are called [Formula: see text]-reversible automata and [Formula: see text]-reversible languages, respectively. The existence of [Formula: see text]-reversible languages which are not [Formula: see text]-reversible is known, for each [Formula: see text]. This gives an infinite hierarchy of weakly irreversible languages, i.e., languages which are [Formula: see text]-reversible for some [Formula: see text]. Conditions characterizing the class of [Formula: see text]-reversible languages, for each fixed [Formula: see text], and the class of weakly irreversible languages are obtained. From these conditions, a procedure that given a finite automaton decides if the accepted language is weakly or strongly (i.e., not weakly) irreversible is described. Furthermore, a construction which allows to transform any finite automaton which is not [Formula: see text]-reversible, but which accepts a [Formula: see text]-reversible language, into an equivalent [Formula: see text]-reversible finite automaton, is presented. <\/jats:p>","DOI":"10.1142\/s0129054122410052","type":"journal-article","created":{"date-parts":[[2022,4,10]],"date-time":"2022-04-10T16:01:11Z","timestamp":1649606471000},"page":"263-284","source":"Crossref","is-referenced-by-count":0,"title":["Weakly and Strongly Irreversible Regular Languages"],"prefix":"10.1142","volume":"33","author":[{"given":"Bruno","family":"Guillon","sequence":"first","affiliation":[{"name":"LIMOS, Universit\u00e9 Clermont-Auvergne, France"}]},{"given":"Giovanna J.","family":"Lavado","sequence":"additional","affiliation":[{"name":"Dipartimento di Informatica, Universit\u00e0 degli Studi di Milano, via Celoria 18, 20133 Milano, Italy"}]},{"given":"Giovanni","family":"Pighizzini","sequence":"additional","affiliation":[{"name":"Dipartimento di Informatica, Universit\u00e0 degli Studi di Milano, via Celoria 18, 20133 Milano, Italy"}]},{"given":"Luca","family":"Prigioniero","sequence":"additional","affiliation":[{"name":"Dipartimento di Informatica, Universit\u00e0 degli Studi di Milano, via Celoria 18, 20133 Milano, Italy"}]}],"member":"219","published-online":{"date-parts":[[2022,4,8]]},"reference":[{"key":"S0129054122410052BIB001","doi-asserted-by":"publisher","DOI":"10.1145\/322326.322334"},{"key":"S0129054122410052BIB002","doi-asserted-by":"publisher","DOI":"10.1147\/rd.176.0525"},{"key":"S0129054122410052BIB003","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054118400063"},{"key":"S0129054122410052BIB004","volume-title":"Introduction to Automata Theory, Languages and Computation","author":"Hopcroft J. E.","year":"1979"},{"key":"S0129054122410052BIB005","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(75)80050-X"},{"key":"S0129054122410052BIB006","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1997.646094"},{"key":"S0129054122410052BIB007","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48057-1_3"},{"key":"S0129054122410052BIB008","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-08494-7_4"},{"key":"S0129054122410052BIB009","doi-asserted-by":"publisher","DOI":"10.1147\/rd.53.0183"},{"key":"S0129054122410052BIB010","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1672"},{"issue":"1","key":"S0129054122410052BIB011","first-page":"145","volume":"22","author":"Lavado G. J.","year":"2017","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"S0129054122410052BIB012","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054119400331"},{"key":"S0129054122410052BIB013","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45465-9_16"},{"key":"S0129054122410052BIB014","doi-asserted-by":"publisher","DOI":"10.1142\/S012905411540002X"},{"key":"S0129054122410052BIB015","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0023844"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054122410052","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,19]],"date-time":"2022-05-19T02:57:42Z","timestamp":1652929062000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0129054122410052"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4]]},"references-count":15,"journal-issue":{"issue":"03n04","published-print":{"date-parts":[[2022,4]]}},"alternative-id":["10.1142\/S0129054122410052"],"URL":"https:\/\/doi.org\/10.1142\/s0129054122410052","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,4]]}}}