{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T01:52:32Z","timestamp":1648950752152},"reference-count":8,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2011,2]]},"abstract":"<jats:p> This article presents approaches to the open problem of whether erasing rules can be eliminated in matrix grammars. The class of languages generated by non-erasing matrix grammars is characterized by the newly introduced linear Petri net grammars. Petri net grammars are known to be equivalent to arbitrary matrix grammars (without appearance checking). In linear Petri net grammars, the marking has to be linear in size with respect to the length of the sentential form. The characterization by linear Petri net grammars is then used to show that applying linear erasing to a Petri net language yields a language generated by a non-erasing matrix grammar. It is also shown that in Petri net grammars (with final markings and arbitrary labeling), erasing rules can be eliminated, which yields two reformulations of the problem of whether erasing rules in matrix grammars can be eliminated. <\/jats:p>","DOI":"10.1142\/s0129054111008118","type":"journal-article","created":{"date-parts":[[2011,2,21]],"date-time":"2011-02-21T05:13:46Z","timestamp":1298265226000},"page":"411-426","source":"Crossref","is-referenced-by-count":1,"title":["TOWARD UNDERSTANDING THE GENERATIVE CAPACITY OF ERASING RULES IN MATRIX GRAMMARS"],"prefix":"10.1142","volume":"22","author":[{"given":"GEORG","family":"ZETZSCHE","sequence":"first","affiliation":[{"name":"Universit\u00e4t Hamburg, Department Informatik, Vogt-K\u00f6lln-Stra\u00dfe 30, 22527, Hamburg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39886-8_13"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-07675-0_3"},{"key":"rf4","first-page":"191","volume":"12","author":"Dassow J\u00fcrgen","journal-title":"Romanian Journal of Information Science and Technology"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(78)90020-8"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1007\/BF01178731"},{"key":"rf7","doi-asserted-by":"crossref","unstructured":"Matthias\u00a0H\u00f6pner, GI Jahrestagung, LNCS\u00a026, ed. Dirk\u00a0Siefkes (Springer-Verlag, Berlin, 1974)\u00a0pp. 113\u2013121.","DOI":"10.1007\/978-3-662-40087-6_7"},{"key":"rf9","doi-asserted-by":"crossref","unstructured":"Manfred\u00a0Kudlek, Carlos\u00a0Mart\u00edn-Vide and Gheorghe\u00a0P\u01ceun, Multiset Processing \u2013 Mathematical, Computer Science, and Molecular Computing Points of View, LNCS\u00a02235 (Springer-Verlag, Berlin, 2001)\u00a0pp. 123\u2013133.","DOI":"10.1007\/3-540-45523-X_7"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1137\/0213029"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054111008118","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T20:34:04Z","timestamp":1565123644000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054111008118"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,2]]},"references-count":8,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2011,2]]}},"alternative-id":["10.1142\/S0129054111008118"],"URL":"https:\/\/doi.org\/10.1142\/s0129054111008118","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,2]]}}}