{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,2,10]],"date-time":"2023-02-10T19:08:44Z","timestamp":1676056124224},"reference-count":17,"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>In this paper, the descriptional complexity of extended finite splicing systems is studied. These systems are known to generate exactly the class of regular languages. Upper and lower bounds are shown relating the size of these splicing systems, defined as the total length of the rules and the initial language of the system, to the size of their equivalent minimal nondeterministic finite automata (NFA). In addition, an accepting model of extended finite splicing systems is studied. Using this variant one can obtain systems which are more than polynomially more succinct than the equivalent NFA or generating extended finite splicing system.<\/jats:p>","DOI":"10.1142\/s0129054108005978","type":"journal-article","created":{"date-parts":[[2008,8,6]],"date-time":"2008-08-06T10:30:40Z","timestamp":1218018640000},"page":"813-826","source":"Crossref","is-referenced-by-count":9,"title":["DESCRIPTIONAL COMPLEXITY OF SPLICING SYSTEMS"],"prefix":"10.1142","volume":"19","author":[{"given":"REMCO","family":"LOOS","sequence":"first","affiliation":[{"name":"Research Group on Mathematical Linguistics, Rovira i Virgili University, Pl. Imperial T\u00e0rraco 1, 43005 Tarragona, Spain"}]},{"given":"ANDREAS","family":"MALCHER","sequence":"additional","affiliation":[{"name":"Fachbereich Informatik und Mathematik, Johann Wolfgang Goethe-Universit\u00e4t, 60054 Frankfurt am Main, Germany"}]},{"given":"DETLEF","family":"WOTSCHKE","sequence":"additional","affiliation":[{"name":"Fachbereich Informatik und Mathematik, Johann Wolfgang Goethe-Universit\u00e4t, 60054 Frankfurt am Main, Germany"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90198-5"},{"key":"rf2","first-page":"97","volume":"1","author":"Bordihn H.","journal-title":"J. Autom. Lang. Comb."},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(91)90054-Z"},{"key":"rf5","first-page":"193","volume":"8","author":"Goldstine J.","journal-title":"J. UCS"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1007\/BF02481771"},{"key":"rf8","volume-title":"Introduction to Automata Theory, Languages and Computation","author":"Hopcroft J. E.","year":"1979"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(83)90026-9"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-3860-5"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.04.014"},{"key":"rf14","doi-asserted-by":"crossref","first-page":"185","DOI":"10.3233\/FI-1997-31206","volume":"31","author":"P\u0103un A.","journal-title":"Fund. Inform."},{"key":"rf15","first-page":"157","volume":"67","author":"P\u0103un A.","journal-title":"Bulletin of the EATCS"},{"key":"rf16","first-page":"27","volume":"1","author":"P\u0103un Gh.","journal-title":"J. Autom. Lang. Comb."},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00082-5"},{"key":"rf18","volume-title":"DNA Computing \u2014 New Computing Paradigms","author":"P\u0103un Gh.","year":"1998"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(95)00079-7"},{"key":"rf20","volume-title":"Formal Languages","author":"Salomaa A.","year":"1973"},{"key":"rf22","series-title":"Lecture Notes","volume-title":"Descriptional Complexity","author":"Wotschke D.","year":"1984"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054108005978","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,7]],"date-time":"2020-05-07T13:19:44Z","timestamp":1588857584000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054108005978"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,8]]},"references-count":17,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2008,8]]}},"alternative-id":["10.1142\/S0129054108005978"],"URL":"https:\/\/doi.org\/10.1142\/s0129054108005978","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,8]]}}}