{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T07:43:51Z","timestamp":1648712631079},"reference-count":8,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Parallel Process. Lett."],"published-print":{"date-parts":[[2016,9]]},"abstract":"<jats:p> Coverability trees offer a finite characterization of all the derivations of a context-free parallel grammar system (CF-PCGS). Their finite nature implies that they necessarily omit some information about these derivations. We demonstrate that the omitted information is most if not all of the time too much, and so coverability trees are not useful as an analysis tool except for their limited use already considered in the paper that introduces them (namely, determining the decidability of certain decision problems over PCGS). We establish this result by invalidating an existing proof that synchronized CF-PCGS are less expressive than context-sensitive grammars. Indeed, we discover that this proof relies on coverability trees for CF-PCGS, but that such coverability trees do not in fact contain enough information to support the proof. <\/jats:p>","DOI":"10.1142\/s0129626416500122","type":"journal-article","created":{"date-parts":[[2016,9,20]],"date-time":"2016-09-20T22:37:55Z","timestamp":1474411075000},"page":"1650012","source":"Crossref","is-referenced-by-count":0,"title":["Limitations of Coverability Trees for Context-Free Parallel Communicating Grammar Systems and Why these Grammar Systems are not Linear Space"],"prefix":"10.1142","volume":"26","author":[{"given":"Stefan D.","family":"Bruda","sequence":"first","affiliation":[{"name":"Department of Computer Science, Bishop\u2019s University 2600 College St, Sherbrooke, Quebec J1M 1Z7, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mary Sarah Ruth","family":"Wilkin","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Bishop\u2019s University 2600 College St, Sherbrooke, Quebec J1M 1Z7, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2016,9,20]]},"reference":[{"issue":"2","key":"p_2","first-page":"199","volume":"15","author":"Cai Liming","year":"1996","journal-title":"Computers and Artificial Intelligence"},{"key":"p_5","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00852-6"},{"key":"p_6","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00193-5"},{"key":"p_8","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00258-8"},{"key":"p_9","first-page":"364","volume":"9","author":"Fischer Patrick C.","year":"1966","journal-title":"Information and Computation"},{"key":"p_11","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00159-5"},{"key":"p_13","first-page":"55","volume":"2","author":"Paun Gheorghe","year":"1989","journal-title":"Seria Matematica-Informatica"},{"key":"p_15","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90243-7"}],"container-title":["Parallel Processing Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129626416500122","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T13:15:17Z","timestamp":1565097317000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129626416500122"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,9]]},"references-count":8,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2016,9,20]]},"published-print":{"date-parts":[[2016,9]]}},"alternative-id":["10.1142\/S0129626416500122"],"URL":"https:\/\/doi.org\/10.1142\/s0129626416500122","relation":{},"ISSN":["0129-6264","1793-642X"],"issn-type":[{"value":"0129-6264","type":"print"},{"value":"1793-642X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,9]]}}}