{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T10:32:15Z","timestamp":1740133935506,"version":"3.37.3"},"reference-count":18,"publisher":"World Scientific Pub Co Pte Ltd","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2020,6]]},"abstract":"<jats:p> One of the most essential classes of problems related to formal languages is the membership problem (also called word problem), i.e., to decide whether a given input word belongs to the language specified, e.g., by a generative grammar. For context-free languages the problem is solved efficiently by various well-known parsing algorithms. However, there are several important languages that are not context-free. The membership problem of the context-sensitive language class is PSPACE-complete, thus, it is believed that it is generally not solvable in an efficient way. There are various language classes between the above mentioned two classes having membership problems with various complexity. One of these classes, the class of permutation languages, is generated by permutation grammars, i.e., context-free grammars extended with permutation rules, where a permutation rule allows to interchange the position of two consecutive nonterminals in the sentential form. In this paper, the membership problem for permutation languages is studied. A proof is presented to show that this problem is NP-complete. <\/jats:p>","DOI":"10.1142\/s0129054120500227","type":"journal-article","created":{"date-parts":[[2020,6,29]],"date-time":"2020-06-29T03:56:55Z","timestamp":1593403015000},"page":"515-525","source":"Crossref","is-referenced-by-count":0,"title":["On the Membership Problem of Permutation Grammars \u2014 A Direct Proof of NP-Completeness"],"prefix":"10.1142","volume":"31","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9494-6440","authenticated-orcid":false,"given":"Benedek","family":"Nagy","sequence":"first","affiliation":[{"name":"Department of Mathematics, Faculty of Arts and Sciences, Eastern Mediterranean University, Famagusta, North Cyprus, via Mersin-10, Turkey"}]}],"member":"219","published-online":{"date-parts":[[2020,6,26]]},"reference":[{"key":"S0129054120500227BIB001","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.04.022"},{"key":"S0129054120500227BIB002","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(86)90062-0"},{"key":"S0129054120500227BIB003","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-74932-2"},{"volume-title":"Abstract volume of the 10th Joint Conference on Mathematics and Computer Science (MaCS)","year":"2014","author":"Fogarasi K.","key":"S0129054120500227BIB004"},{"key":"S0129054120500227BIB005","doi-asserted-by":"publisher","DOI":"10.1137\/0204035"},{"volume-title":"Introduction to Automata Theory, Languages, and Computation","year":"1979","author":"Hopcroft J. E.","key":"S0129054120500227BIB006"},{"key":"S0129054120500227BIB008","doi-asserted-by":"publisher","DOI":"10.3233\/FI-2014-992"},{"key":"S0129054120500227BIB009","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-22360-5_18"},{"key":"S0129054120500227BIB010","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/2018016"},{"key":"S0129054120500227BIB011","doi-asserted-by":"publisher","DOI":"10.1007\/BF01936139"},{"key":"S0129054120500227BIB012","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4939-0369-6"},{"key":"S0129054120500227BIB013","first-page":"563","volume-title":"Proc. CINTI 2007: 8th Int. Symp. of Hungarian Researchers on Computational Intelligence and Informatics","author":"Nagy B.","year":"2007"},{"key":"S0129054120500227BIB014","first-page":"175","volume":"14","author":"Nagy B.","year":"2009","journal-title":"J. Autom. Lang. Combin."},{"key":"S0129054120500227BIB015","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02478-8_63"},{"key":"S0129054120500227BIB016","doi-asserted-by":"publisher","DOI":"10.1142\/9789814317610_0012"},{"key":"S0129054120500227BIB017","first-page":"135","volume-title":"Bio-Inspired Models for Natural and Formal Languages","author":"Nagy B.","year":"2011"},{"volume-title":"Abstract volume of the Int. Workshop in honor of Masami Ito\u2019s 77th birthday and P\u00e1l D\u00f6m\u00f6si\u2019s 75th birthday: DLT\u2019s Satellite Workshop in Kyoto","author":"Nagy B.","key":"S0129054120500227BIB018"},{"key":"S0129054120500227BIB019","doi-asserted-by":"publisher","DOI":"10.1145\/512760.512780"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054120500227","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,7,9]],"date-time":"2020-07-09T09:27:43Z","timestamp":1594286863000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054120500227"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6]]},"references-count":18,"journal-issue":{"issue":"04","published-print":{"date-parts":[[2020,6]]}},"alternative-id":["10.1142\/S0129054120500227"],"URL":"https:\/\/doi.org\/10.1142\/s0129054120500227","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"type":"print","value":"0129-0541"},{"type":"electronic","value":"1793-6373"}],"subject":[],"published":{"date-parts":[[2020,6]]}}}