{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,25]],"date-time":"2025-04-25T04:10:54Z","timestamp":1745554254928},"reference-count":11,"publisher":"World Scientific Pub Co Pte Lt","issue":"07","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2013,11]]},"abstract":"<jats:p> We shall show that (i) there exists a binary NP-complete language [Formula: see text] such that its unary coded version [Formula: see text] is in ASPACE( log log n), (ii) if P \u2260 NP, there exists a binary language [Formula: see text] such that its unary version [Formula: see text] is in ASPACE( log log n), while the language [Formula: see text] itself is not in ASPACE( log n). As a consequence, under assumption that P \u2260 NP, the standard space translation between unary and binary languages does not work for alternating machines with small space; the equivalence [Formula: see text] is valid only if s(n) \u2208 \u03a9(n). This is quite different from deterministic and nondeterministic machines, for which the corresponding equivalence holds for each s(n) \u2208 \u03a9( log n), and hence for s( log n) \u2208 \u03a9( log log n). Under assumption that NP \u2260 co-NP, we also show that binary versions of unary languages in ASPACE( log log n) form a complexity class not contained in NP. <\/jats:p>","DOI":"10.1142\/s0129054113400376","type":"journal-article","created":{"date-parts":[[2014,2,27]],"date-time":"2014-02-27T07:16:43Z","timestamp":1393485403000},"page":"1167-1182","source":"Crossref","is-referenced-by-count":5,"title":["UNARY CODED NP-COMPLETE LANGUAGES IN ASPACE(<font>log log<\/font> n)"],"prefix":"10.1142","volume":"24","author":[{"given":"VILIAM","family":"GEFFERT","sequence":"first","affiliation":[{"name":"Department of Computer Science, P. J. \u0160af\u00e1rik University, Jesenn\u00e1 5, 04154 Ko\u0161ice, Slovakia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"DANA","family":"PARDUBSK\u00c1","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Comenius University, Mlynsk\u00e1 dolina, 84248 Bratislava, Slovakia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2014,2,26]]},"reference":[{"key":"p_1","first-page":"781","volume":"160","author":"Agrawal M.","year":"2004","journal-title":"Math."},{"key":"p_3","first-page":"61","volume":"74","author":"Allender E.","year":"2001","journal-title":"Bull. Eur. Assoc. Theoret. Comput. Sci."},{"key":"p_4","doi-asserted-by":"publisher","DOI":"10.1145\/322234.322243"},{"key":"p_5","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90391-E"},{"key":"p_6","first-page":"259","volume":"35","author":"Chiu A.","year":"2001","journal-title":"Appl."},{"key":"p_7","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)00021-2"},{"key":"p_8","first-page":"127","volume":"142","author":"Geffert V.","year":"1998","journal-title":"Comput."},{"key":"p_9","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00402-4"},{"key":"p_14","doi-asserted-by":"publisher","DOI":"10.1137\/0222011"},{"key":"p_15","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793252444"},{"key":"p_16","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(70)80006-X"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054113400376","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T19:00:40Z","timestamp":1565118040000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054113400376"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,11]]},"references-count":11,"journal-issue":{"issue":"07","published-online":{"date-parts":[[2014,2,26]]},"published-print":{"date-parts":[[2013,11]]}},"alternative-id":["10.1142\/S0129054113400376"],"URL":"https:\/\/doi.org\/10.1142\/s0129054113400376","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,11]]}}}