{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T15:09:17Z","timestamp":1648825757123},"reference-count":14,"publisher":"World Scientific Pub Co Pte Lt","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2007,12]]},"abstract":"<jats:p> We introduce a new type of finite copying parallel rewriting system, i. e., grammars with linked nonterminals, which extend the generative capacity of context-free grammars. They can be thought of as having sentential forms where some instances of a nonterminal may be linked. The context-free-like productions replace a nonterminal together with its connected instances. New links are only established between symbols of the derived subforms. A natural limitation is to bound the degree of synchronous rewriting. We present an infinite degree hierarchy of separated language families with the property that degree one characterizes the family of regular and degree two the family of context-free languages. Furthermore, the hierarchy is a refinement of the known hierarchy of finite copying rewriting systems. Several closure properties known from equivalent systems are summarized. <\/jats:p>","DOI":"10.1142\/s0129054107005315","type":"journal-article","created":{"date-parts":[[2007,10,29]],"date-time":"2007-10-29T03:37:41Z","timestamp":1193629061000},"page":"1271-1282","source":"Crossref","is-referenced-by-count":1,"title":["CONTEXT-FREE GRAMMARS WITH LINKED NONTERMINALS"],"prefix":"10.1142","volume":"18","author":[{"given":"ANDREAS","family":"KLEIN","sequence":"first","affiliation":[{"name":"Department of Pure Mathematics and Computer Algebra, Ghent University, Krijgslaan 281-S22, 9000 Ghent, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MARTIN","family":"KUTRIB","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Informatik, Universit\u00e4t Giessen, Arndtstra\u00dfe 2, 35392 Giessen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(71)90706-6"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1137\/0218038"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80041-3"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(73)90917-0"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-74932-2"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-07675-0_3"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59126-6_3"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90058-6"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1145\/321127.321132"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1145\/321386.321403"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(75)80019-5"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1145\/321356.321364"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00190-4"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1080\/00207167708803138"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054107005315","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T20:43:01Z","timestamp":1565124181000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054107005315"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,12]]},"references-count":14,"journal-issue":{"issue":"06","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2007,12]]}},"alternative-id":["10.1142\/S0129054107005315"],"URL":"https:\/\/doi.org\/10.1142\/s0129054107005315","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,12]]}}}