{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,29]],"date-time":"2024-06-29T02:15:37Z","timestamp":1719627337391},"reference-count":12,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2012,1]]},"abstract":"<jats:p> Finite-state complexity is a variant of algorithmic information theory obtained by replacing Turing machines with finite transducers. We consider the number of states needed for transducers used in minimal descriptions of arbitrary strings and, as our main result, show that the state-size hierarchy with respect to a standard encoding is infinite. We consider corresponding hierarchies yielded by more general computable encodings and establish that for a suitably chosen computable encoding every level of the state-size hierarchy can be strict. <\/jats:p>","DOI":"10.1142\/s0129054112400035","type":"journal-article","created":{"date-parts":[[2012,2,20]],"date-time":"2012-02-20T05:57:11Z","timestamp":1329717431000},"page":"37-50","source":"Crossref","is-referenced-by-count":3,"title":["STATE-SIZE HIERARCHY FOR FINITE-STATE COMPLEXITY"],"prefix":"10.1142","volume":"23","author":[{"given":"CRISTIAN S.","family":"CALUDE","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Auckland, New Zealand"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"KAI","family":"SALOMAA","sequence":"additional","affiliation":[{"name":"School of Computing, Queen's University, Kingston, Ontario, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"TANIA K.","family":"ROBLOT","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Auckland, New Zealand"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2012,4,6]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546563"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.040"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-663-09367-1"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04978-5"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511608858"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2007.05.003"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-26677-0"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1145\/507457.507473"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1007\/BF02984830"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0046"},{"key":"rf17","first-page":"537","volume":"6","author":"Shallit J.","journal-title":"J. Automata, Languages and Combinatorics"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59136-5_2"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054112400035","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T09:30:09Z","timestamp":1565170209000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054112400035"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1]]},"references-count":12,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2012,4,6]]},"published-print":{"date-parts":[[2012,1]]}},"alternative-id":["10.1142\/S0129054112400035"],"URL":"https:\/\/doi.org\/10.1142\/s0129054112400035","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,1]]}}}