{"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":1740133935756,"version":"3.37.3"},"reference-count":16,"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> Two-dimensional general row jumping finite automata were recently introduced as an interesting computational model for accepting two-dimensional languages. These automata are nondeterministic. They guess an order in which rows of the input array are read and they jump to the next row only after reading all symbols in the previous row. In each row, they choose, also nondeterministically, an order in which segments of the row are read. In this paper, we study the membership problem for these automata. We show that each general row jumping finite automaton can be simulated by a nondeterministic Turing machine with space bounded by the logarithm. This means that the fixed membership problems for such automata are in NL, and so in P. On the other hand, we show that the uniform membership problem is NP-complete. <\/jats:p>","DOI":"10.1142\/s0129054120500239","type":"journal-article","created":{"date-parts":[[2020,6,30]],"date-time":"2020-06-30T03:13:03Z","timestamp":1593486783000},"page":"527-538","source":"Crossref","is-referenced-by-count":0,"title":["Membership Problem for Two-Dimensional General Row Jumping Finite Automata"],"prefix":"10.1142","volume":"31","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2114-5626","authenticated-orcid":false,"given":"Grzegorz","family":"Madejski","sequence":"first","affiliation":[{"name":"Institute of Informatics, Faculty of Mathematics, Physics, and Informatics, University of Gda\u0144sk, 80-308 Gda\u0144sk, Poland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4884-3811","authenticated-orcid":false,"given":"Andrzej","family":"Szepietowski","sequence":"additional","affiliation":[{"name":"Institute of Informatics, Faculty of Mathematics, Physics, and Informatics, University of Gda\u0144sk, 80-308 Gda\u0144sk, Poland"}]}],"member":"219","published-online":{"date-parts":[[2020,6,30]]},"reference":[{"key":"S0129054120500239BIB001","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054116400165"},{"key":"S0129054120500239BIB002","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-22360-5_8"},{"key":"S0129054120500239BIB003","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2017.07.011"},{"key":"S0129054120500239BIB004","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2016.07.006"},{"volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","year":"1979","author":"Garey M. R.","key":"S0129054120500239BIB006"},{"key":"S0129054120500239BIB007","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59126-6_4"},{"key":"S0129054120500239BIB008","series-title":"Addison-Wesley series in computer science, Addison-Wesley series in computer science","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"Hopcroft J. E.","year":"2001","edition":"2"},{"key":"S0129054120500239BIB009","doi-asserted-by":"publisher","DOI":"10.13164\/ma.2016.08"},{"key":"S0129054120500239BIB010","doi-asserted-by":"publisher","DOI":"10.1504\/IJAISC.2017.088890"},{"key":"S0129054120500239BIB011","doi-asserted-by":"publisher","DOI":"10.1137\/0217058"},{"key":"S0129054120500239BIB012","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24897-9_9"},{"key":"S0129054120500239BIB015","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054112500244"},{"key":"S0129054120500239BIB016","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4939-0369-6"},{"key":"S0129054120500239BIB017","doi-asserted-by":"publisher","DOI":"10.1002\/9780470590416"},{"key":"S0129054120500239BIB018","doi-asserted-by":"publisher","DOI":"10.1007\/BF00299636"},{"key":"S0129054120500239BIB019","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-58355-6"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054120500239","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,7,9]],"date-time":"2020-07-09T09:27:48Z","timestamp":1594286868000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054120500239"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6]]},"references-count":16,"journal-issue":{"issue":"04","published-print":{"date-parts":[[2020,6]]}},"alternative-id":["10.1142\/S0129054120500239"],"URL":"https:\/\/doi.org\/10.1142\/s0129054120500239","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"type":"print","value":"0129-0541"},{"type":"electronic","value":"1793-6373"}],"subject":[],"published":{"date-parts":[[2020,6]]}}}