{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T12:03:13Z","timestamp":1709812993800},"reference-count":19,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2005,6]]},"abstract":"<jats:p> We investigate the operation problem for linear and deterministic context-free languages: Fix an operation on formal languages. Given linear (deterministic, respectively) context-free languages, is the application of this operation to the given languages still a linear (deterministic, respectively) context-free language? Besides the classical operations, for which the linear and deterministic context-free languages are not closed, we also consider the recently introduced root and power operation. We show non-semi-decidability, to be more precise, we show completeness for the second level of the arithmetic hierarchy for all of the aforementioned operations, except for the power operation, if the underlying alphabet contains at least two letters. The result for the power operation solves an open problem stated in Theoret. Comput. Sci.314 (2004) 445\u2013449. <\/jats:p>","DOI":"10.1142\/s0129054105003078","type":"journal-article","created":{"date-parts":[[2005,7,5]],"date-time":"2005-07-05T10:52:13Z","timestamp":1120560733000},"page":"423-440","source":"Crossref","is-referenced-by-count":5,"title":["UNSOLVABILITY LEVELS OF OPERATION PROBLEMS FOR SUBCLASSES OF CONTEXT-FREE LANGUAGES"],"prefix":"10.1142","volume":"16","author":[{"given":"HENNING","family":"BORDIHN","sequence":"first","affiliation":[{"name":"Institut f\u00fcr Informatik, Universit\u00e4t Potsdam, August-Bebel-Stra\u00dfe 89, D-14482 Potsdam, Germany"}]},{"given":"MARKUS","family":"HOLZER","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Informatik, Technische Universit\u00e4t M\u00fcnchen, Boltzmannstra\u00dfe 3, D-85748 Garching bei M\u00fcnchen, Germany"}]},{"given":"MARTIN","family":"KUTRIB","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Informatik, Universit\u00e4t Giessen, Arndtstra\u00dfe 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.1145\/322307.322315"},{"key":"rf3","first-page":"143","volume":"14","author":"Bar-Hillel Y.","journal-title":"Zeitschrift f\u00fcr Phonetik, Sprachwissenschaft und Kommunikationsforschung"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2003.08.005"},{"key":"rf8","first-page":"81","volume":"14","author":"Cudia D. F.","journal-title":"Notices Amer. Math. Soc."},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1145\/321556.321560"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1145\/321479.321490"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1145\/321150.321153"},{"key":"rf13","first-page":"333","volume":"113","author":"Ginsburg S.","journal-title":"Trans. Amer. Math. Soc."},{"key":"rf14","first-page":"117","volume":"6","author":"Greibach S. A.","journal-title":"Inform. Control"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1145\/321356.321365"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(64)90422-X"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1090\/psapm\/019\/0235938"},{"key":"rf18","volume-title":"Introduction to Automata Theory, Languages and Computation","author":"Hopcroft J. E.","year":"1979"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1145\/321406.321411"},{"key":"rf21","volume-title":"Theory of Recursive Functions and Effective Computability","author":"Rogers H.","year":"1967"},{"key":"rf22","volume-title":"Formal Languages","author":"Salomaa A.","year":"1973"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00285-1"},{"key":"rf24","volume-title":"Theory of Computation","author":"Wood D.","year":"1987"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054105003078","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T20:39:27Z","timestamp":1565123967000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054105003078"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,6]]},"references-count":19,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2005,6]]}},"alternative-id":["10.1142\/S0129054105003078"],"URL":"https:\/\/doi.org\/10.1142\/s0129054105003078","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,6]]}}}