{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T03:10:56Z","timestamp":1775617856742,"version":"3.50.1"},"reference-count":11,"publisher":"World Scientific Pub Co Pte Lt","issue":"06n07","funder":[{"name":"Russian Foundation for Basic Research","award":["16-01-00795"],"award-info":[{"award-number":["16-01-00795"]}]},{"DOI":"10.13039\/501100003443","name":"Ministry of Education and Science of the Russian Federation","doi-asserted-by":"crossref","award":["1.3253.2017"],"award-info":[{"award-number":["1.3253.2017"]}],"id":[{"id":"10.13039\/501100003443","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2019,9]]},"abstract":"<jats:p>We prove PSPACE-completeness of checking whether a given ideal language serves as the language of reset words for some automaton with at most four states over a binary alphabet. We compare the reset complexity and the state complexity for languages related to slowly synchronizing automata.<\/jats:p>","DOI":"10.1142\/s0129054119400343","type":"journal-article","created":{"date-parts":[[2019,9,19]],"date-time":"2019-09-19T07:06:43Z","timestamp":1568876803000},"page":"1177-1196","source":"Crossref","is-referenced-by-count":12,"title":["Reset Complexity of Ideal Languages Over a Binary Alphabet"],"prefix":"10.1142","volume":"30","author":[{"given":"Marina","family":"Maslennikova","sequence":"first","affiliation":[{"name":"Institute of Natural Sciences and Mathematics, Ural Federal University, 620000 Ekaterinburg, Russia"}]}],"member":"219","published-online":{"date-parts":[[2019,9,19]]},"reference":[{"key":"S0129054119400343BIB001","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15155-2_7"},{"key":"S0129054119400343BIB002","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-41114-9_1"},{"issue":"3","key":"S0129054119400343BIB004","doi-asserted-by":"crossref","first-page":"P3.12","DOI":"10.37236\/5616","volume":"23","author":"Don H.","year":"2016","journal-title":"Electr. J. Comb."},{"key":"S0129054119400343BIB005","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48057-1_26"},{"key":"S0129054119400343BIB006","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1977.16"},{"key":"S0129054119400343BIB008","volume-title":"Int. Conf. SOFSEM","author":"Maslennikova M. I.","year":"2012"},{"key":"S0129054119400343BIB009","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-09704-6_27"},{"key":"S0129054119400343BIB010","doi-asserted-by":"publisher","DOI":"10.1109\/SWAT.1971.11"},{"key":"S0129054119400343BIB012","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-444-88074-1.50006-8"},{"key":"S0129054119400343BIB013","doi-asserted-by":"publisher","DOI":"10.1145\/800125.804029"},{"key":"S0129054119400343BIB014","series-title":"LNCS","first-page":"11","volume-title":"LATA 2008","volume":"5196","author":"Volkov M. V.","year":"2005"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054119400343","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,21]],"date-time":"2021-01-21T07:23:24Z","timestamp":1611213804000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054119400343"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9]]},"references-count":11,"journal-issue":{"issue":"06n07","published-print":{"date-parts":[[2019,9]]}},"alternative-id":["10.1142\/S0129054119400343"],"URL":"https:\/\/doi.org\/10.1142\/s0129054119400343","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,9]]}}}