{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,5,19]],"date-time":"2022-05-19T03:12:22Z","timestamp":1652929942362},"reference-count":22,"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":" Reversible forms of computations are often interesting from an energy efficiency point of view. When the computation device in question is an automaton, it is known that the minimal reversible automaton recognizing a given language is not necessarily unique, moreover, there are languages having arbitrarily large reversible recognizers possessing no nontrivial \u201creversible\u201d congruence. Building atop on our earlier result, we show that the corresponding decision problem is [Formula: see text]-complete, and that even in the case when there are only finitely many such reversible recognizers, the largest one among them can be exponentially larger than the minimal automaton. Both results hold for the case of binary alphabets. <\/jats:p>","DOI":"10.1142\/s0129054122410040","type":"journal-article","created":{"date-parts":[[2022,5,15]],"date-time":"2022-05-15T03:40:05Z","timestamp":1652586005000},"page":"247-262","source":"Crossref","is-referenced-by-count":0,"title":["Descriptive Complexity of Reversible Languages Having Finitely Many Reduced Automata"],"prefix":"10.1142","volume":"33","author":[{"given":"Kitti","family":"Gelle","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Szeged, Hungary"}]},{"given":"Szabolcs","family":"Iv\u00e1n","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Szeged, Hungary"}]}],"member":"219","published-online":{"date-parts":[[2022,5,12]]},"reference":[{"key":"S0129054122410040BIB001","doi-asserted-by":"publisher","DOI":"10.1145\/322326.322334"},{"key":"S0129054122410040BIB002","doi-asserted-by":"publisher","DOI":"10.1147\/rd.176.0525"},{"key":"S0129054122410040BIB003","doi-asserted-by":"publisher","DOI":"10.1016\/S1355-2198(03)00039-X"},{"key":"S0129054122410040BIB004","doi-asserted-by":"publisher","DOI":"10.1016\/S1355-2198(01)00023-5"},{"key":"S0129054122410040BIB005","doi-asserted-by":"publisher","DOI":"10.1016\/S1355-2198(98)00026-4"},{"key":"S0129054122410040BIB006","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.252.13"},{"key":"S0129054122410040BIB007","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21500-6_22"},{"key":"S0129054122410040BIB008","volume-title":"Introduction to Automata Theory, Languages and Computation","author":"Hopcroft J. E.","year":"1979"},{"key":"S0129054122410040BIB009","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1997.646094"},{"key":"S0129054122410040BIB010","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-13350-8_7"},{"key":"S0129054122410040BIB011","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48057-1_3"},{"key":"S0129054122410040BIB012","doi-asserted-by":"publisher","DOI":"10.1016\/j.shpsb.2006.03.007"},{"key":"S0129054122410040BIB013","doi-asserted-by":"publisher","DOI":"10.1147\/rd.53.0183"},{"key":"S0129054122410040BIB014","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1672"},{"key":"S0129054122410040BIB016","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.252.15"},{"key":"S0129054122410040BIB017","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-60252-3_19"},{"key":"S0129054122410040BIB018","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45465-9_16"},{"key":"S0129054122410040BIB019","volume-title":"Quantum Computation and Quantum Information","author":"Nielsen M.","year":"2000"},{"key":"S0129054122410040BIB020","doi-asserted-by":"publisher","DOI":"10.1016\/j.shpsb.2004.12.002"},{"key":"S0129054122410040BIB021","doi-asserted-by":"publisher","DOI":"10.1016\/j.shpsb.2011.05.002"},{"key":"S0129054122410040BIB022","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0023844"},{"key":"S0129054122410040BIB023","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.2010.0577"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054122410040","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,19]],"date-time":"2022-05-19T02:57:45Z","timestamp":1652929065000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0129054122410040"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4]]},"references-count":22,"journal-issue":{"issue":"03n04","published-print":{"date-parts":[[2022,4]]}},"alternative-id":["10.1142\/S0129054122410040"],"URL":"https:\/\/doi.org\/10.1142\/s0129054122410040","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,4]]}}}