{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T11:06:54Z","timestamp":1649156814719},"reference-count":17,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2019,1]]},"abstract":"<jats:p> Permitting semi-conditional grammars (pSCGs) are extensions of context-free grammars where each rule is associated with a word [Formula: see text] and such a rule can be applied to a sentential form [Formula: see text] only if [Formula: see text] is a subword of [Formula: see text]. We consider permitting generalized SCGs (pgSCGs) where each rule [Formula: see text] is associated with a set of words [Formula: see text] and [Formula: see text] is applicable only if every word in [Formula: see text] occurs in [Formula: see text]. We investigate the generative power of pgSCGs with no erasing rules and prove a pumping lemma for their languages. Using this lemma we show that pgSCGs are strictly weaker than context-sensitive grammars. This solves a long-lasting open problem concerning the generative power of pSCGs. Moreover, we give a comparison of the generating power of pgSCGs and that of forbidding random context grammars with no erasing rules. <\/jats:p>","DOI":"10.1142\/s0129054119400045","type":"journal-article","created":{"date-parts":[[2019,3,5]],"date-time":"2019-03-05T04:13:14Z","timestamp":1551759194000},"page":"73-92","source":"Crossref","is-referenced-by-count":1,"title":["A Pumping Lemma for Permitting Semi-Conditional Languages"],"prefix":"10.1142","volume":"30","author":[{"given":"Zsolt","family":"Gazdag","sequence":"first","affiliation":[{"name":"Department of Foundations of Computer Science, University of Szeged, 13 Dugonics Square, Szeged H-6720, Hungary"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kriszti\u00e1n","family":"Tichler","sequence":"additional","affiliation":[{"name":"Department of Algorithms and Their Applications, E\u00f6tv\u00f6s Lor\u00e1nd University, Budapest, Hungary"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erzs\u00e9bet","family":"Csuhaj-Varj\u00fa","sequence":"additional","affiliation":[{"name":"Department of Algorithms and Their Applications, E\u00f6tv\u00f6s Lor\u00e1nd University, Budapest, Hungary"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2019,3,5]]},"reference":[{"key":"S0129054119400045BIB001","first-page":"199","volume-title":"Developments in Language Theory, Magdeburg, Germany","author":"Bordihn H.","year":"1996"},{"key":"S0129054119400045BIB002","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2011.05.008"},{"key":"S0129054119400045BIB003","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-74932-2"},{"key":"S0129054119400045BIB004","doi-asserted-by":"publisher","DOI":"10.2307\/2370405"},{"key":"S0129054119400045BIB005","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00160-1"},{"key":"S0129054119400045BIB006","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00171-2"},{"key":"S0129054119400045BIB007","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(68)90439-7"},{"issue":"1","key":"S0129054119400045BIB009","first-page":"81","volume":"19","author":"Gazdag Z.","year":"2014","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"S0129054119400045BIB011","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-2.1.326"},{"key":"S0129054119400045BIB012","volume-title":"Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition","author":"Jurafsky D.","year":"2000"},{"issue":"2","key":"S0129054119400045BIB014","first-page":"210","volume":"95","author":"Kruskal J. B.","year":"1960","journal-title":"Transactions of the American Mathematical Society"},{"key":"S0129054119400045BIB015","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.04.001"},{"key":"S0129054119400045BIB016","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(79)90664-8"},{"key":"S0129054119400045BIB017","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90056-8"},{"key":"S0129054119400045BIB018","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-07675-0"},{"key":"S0129054119400045BIB019","volume-title":"Formal Languages","author":"Salomaa A.","year":"1973"},{"key":"S0129054119400045BIB020","first-page":"66","volume":"71","author":"van der Walt A.","year":"1972","journal-title":"Inform. Process."}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054119400045","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T14:35:29Z","timestamp":1565102129000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054119400045"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1]]},"references-count":17,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2019,3,5]]},"published-print":{"date-parts":[[2019,1]]}},"alternative-id":["10.1142\/S0129054119400045"],"URL":"https:\/\/doi.org\/10.1142\/s0129054119400045","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1]]}}}