{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T10:32:12Z","timestamp":1740133932372,"version":"3.37.3"},"reference-count":4,"publisher":"World Scientific Pub Co Pte Ltd","issue":"07","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2018,11]]},"abstract":"<jats:p> Let [Formula: see text] be an alphabet having at least three symbols. Let [Formula: see text] denote the family of all context-free languages over [Formula: see text], [Formula: see text] denote the family of all parsing expression grammars over [Formula: see text], and [Formula: see text] denote the family of all parsing expression languages over [Formula: see text]. Let [Formula: see text] satisfy [Formula: see text] and \u201c[Formula: see text]\u201d, where we use the double-quoted \u201c[Formula: see text]\u201d in the sense that we can effectively find some [Formula: see text] such that [Formula: see text]. Then the following problem is shown to be undecidable: Given [Formula: see text], decide if [Formula: see text]. In particular, the following basic problem is shown to be undecidable: Given [Formula: see text], decide if [Formula: see text]. <\/jats:p>","DOI":"10.1142\/s0129054118500296","type":"journal-article","created":{"date-parts":[[2018,11,11]],"date-time":"2018-11-11T23:18:10Z","timestamp":1541978290000},"page":"1203-1213","source":"Crossref","is-referenced-by-count":1,"title":["Context-Freeness of Parsing Expression Languages is Undecidable"],"prefix":"10.1142","volume":"29","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6016-1306","authenticated-orcid":false,"given":"Toshihiro","family":"Koga","sequence":"first","affiliation":[{"name":"#D-804 Purimasitei 4-1-1, Nagatsutaminamidai, Midori-ku, Yokohama-shi, Kanagawa-ken 226-0018, Japan"}]}],"member":"219","published-online":{"date-parts":[[2018,11,11]]},"reference":[{"key":"S0129054118500296BIB001","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/1982160100031"},{"key":"S0129054118500296BIB003","doi-asserted-by":"publisher","DOI":"10.1145\/982962.964011"},{"issue":"1","key":"S0129054118500296BIB004","first-page":"1","volume":"2","author":"Greibach S.","year":"1968","journal-title":"Theory of Computing Systems"},{"volume-title":"Introduction to Automata Theory, Languages, and Computation","year":"2006","author":"Hopcroft J. E.","key":"S0129054118500296BIB005"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054118500296","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T08:49:26Z","timestamp":1565167766000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054118500296"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,11]]},"references-count":4,"journal-issue":{"issue":"07","published-online":{"date-parts":[[2018,11,11]]},"published-print":{"date-parts":[[2018,11]]}},"alternative-id":["10.1142\/S0129054118500296"],"URL":"https:\/\/doi.org\/10.1142\/s0129054118500296","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"type":"print","value":"0129-0541"},{"type":"electronic","value":"1793-6373"}],"subject":[],"published":{"date-parts":[[2018,11]]}}}