{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:25:06Z","timestamp":1759638306669},"reference-count":24,"publisher":"World Scientific Pub Co Pte Lt","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2005,10]]},"abstract":"<jats:p> Non-recursive trade-offs between different representations of languages reveal a basic phenomenon. The gain in economy of description can be arbitrary. The purpose of this paper is to survey the main aspects and results regarding different representations of languages whose relative succinctness is not recursively bounded. Basic properties of descriptional systems and reasonable size measures are addressed, and the unified fundamental proof schemes emerging from the literature are presented. A comprehensive overview of results is given. Finally, some new results are shown. In particular, it is proved that between each two levels of the infinite one-way k-head finite automata hierarchies there is a non-recursive trade-off. Moreover, non-recursive trade-offs are shown between nondeterministic 2-head and deterministic k-head automata. <\/jats:p>","DOI":"10.1142\/s0129054105003406","type":"journal-article","created":{"date-parts":[[2005,10,13]],"date-time":"2005-10-13T11:41:41Z","timestamp":1129203701000},"page":"957-973","source":"Crossref","is-referenced-by-count":29,"title":["THE PHENOMENON OF NON-RECURSIVE TRADE-OFFS"],"prefix":"10.1142","volume":"16","author":[{"given":"MARTIN","family":"KUTRIB","sequence":"first","affiliation":[{"name":"Institut f\u00fcr Informatik,  Universit\u00e4t Giessen, Arndtstr. 2, D-35392 Giessen, Germany"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80027-9"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(01)00156-9"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1007\/BF01371727"},{"key":"rf6","volume-title":"Grammar Systems","author":"Csuhaj-Varju E.","year":"1994"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-74932-2"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(66)80019-0"},{"key":"rf9","first-page":"193","volume":"8","author":"Goldstine J.","journal-title":"J. UCS"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1145\/321356.321365"},{"key":"rf11","series-title":"Proc. Symposia in Applied Mathematics","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1090\/psapm\/019\/0235938","volume":"19","author":"Hartmanis J.","year":"1967"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1137\/0209010"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(83)90016-6"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00267-8"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054103002199"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.04.013"},{"key":"rf21","first-page":"549","volume":"7","author":"Malcher A.","journal-title":"J. Autom., Lang. Comb."},{"key":"rf23","first-page":"721","volume":"87","author":"Malcher A.","journal-title":"Trans. IEICE"},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(75)90013-4"},{"key":"rf26","volume-title":"Formal Languages","author":"Salomaa A.","year":"1973"},{"key":"rf27","doi-asserted-by":"publisher","DOI":"10.1137\/0206039"},{"key":"rf28","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(67)90591-8"},{"key":"rf30","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(76)90173-X"},{"key":"rf31","doi-asserted-by":"publisher","DOI":"10.1145\/322063.322076"},{"key":"rf32","first-page":"221","volume":"6","author":"Yu S.","journal-title":"J. Autom., Lang. Comb."},{"key":"rf33","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)00011-F"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054105003406","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:41:21Z","timestamp":1565138481000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054105003406"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,10]]},"references-count":24,"journal-issue":{"issue":"05","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2005,10]]}},"alternative-id":["10.1142\/S0129054105003406"],"URL":"https:\/\/doi.org\/10.1142\/s0129054105003406","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,10]]}}}