{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T11:40:40Z","timestamp":1742384440926},"reference-count":14,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2008,8]]},"abstract":"<jats:p> Insertion-deletion operations are much investigated in linguistics and in DNA computing and several characterizations of Turing computability and characterizations or representations of languages in Chomsky hierarchy were obtained in this framework. <\/jats:p><jats:p> In this note we contribute to this research direction with a new characterization of this type, as well as with representations of regular and context-free languages, mainly starting from context-free insertion systems of as small as possible complexity. For instance, each recursively enumerable language L can be represented in a way similar to the celebrated Chomsky-Sch\u00fctzenberger representation of context-free languages, i.e., in the form L = h(L(\u03b3) \u2229 D), where \u03b3 is an insertion system of weight (3, 0) (at most three symbols are inserted in a context of length zero), h is a projection, and D is a Dyck language. A similar representation can be obtained for regular languages, involving insertion systems of weight (2,0) and star languages, as well as for context-free languages \u2013 this time using insertion systems of weight (3, 0) and star languages. <\/jats:p>","DOI":"10.1142\/s0129054108006005","type":"journal-article","created":{"date-parts":[[2008,8,6]],"date-time":"2008-08-06T10:30:40Z","timestamp":1218018640000},"page":"859-871","source":"Crossref","is-referenced-by-count":13,"title":["REPRESENTATIONS AND CHARACTERIZATIONS OF LANGUAGES IN CHOMSKY HIERARCHY BY MEANS OF INSERTION-DELETION SYSTEMS"],"prefix":"10.1142","volume":"19","author":[{"given":"GHEORGHE","family":"P\u0102UN","sequence":"first","affiliation":[{"name":"Institute of Mathematics of the Romanian Academy, PO Box 1-764, 014700 Bucharest, Romania"},{"name":"Department of Computer Science and Artificial Intelligence, Univ. of Sevilla, Avda Reina Mercedes s\/n, 41012 Sevilla, Spain"}]},{"given":"MARIO J.","family":"P\u00c9REZ-JIM\u00c9NEZ","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Artificial Intelligence, University of Sevilla, Avda Reina Mercedes s\/n, 41012 Sevilla, Spain"}]},{"given":"TAKASHI","family":"YOKOMORI","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Faculty of Education and Integrated Arts and Sciences, Waseda University, 1-6-1 Nishiwaseda, Shinjuku-ku, Tokyo 169-8050, Japan"}]}],"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","first-page":"38","author":"Galiukschov B. S.","journal-title":"Mat. logica i mat. ling."},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90018-0"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1996.0091"},{"key":"rf6","first-page":"1525","volume":"14","author":"Marcus S.","journal-title":"Rev. Roum. Math. Pures Appl."},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.06.031"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00079-0"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90119-2"},{"key":"rf10","first-page":"1424","volume":"44","author":"Onodera K.","journal-title":"IPSJ Journal"},{"key":"rf11","volume-title":"Marcus Contextual Grammars","author":"P\u01ceun Gh.","year":"1998"},{"key":"rf12","volume-title":"DNA Computing. New Computing Paradigms","author":"P\u01ceun Gh.","year":"1998"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59126-6"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1023\/B:NACO.0000006769.27984.23"},{"key":"rf16","volume-title":"Computational Complexity","author":"Wagner K.","year":"1986"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054108006005","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T15:23:51Z","timestamp":1565191431000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054108006005"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,8]]},"references-count":14,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2008,8]]}},"alternative-id":["10.1142\/S0129054108006005"],"URL":"https:\/\/doi.org\/10.1142\/s0129054108006005","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,8]]}}}