We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Membership Problem for Two-Dimensional General Row Jumping Finite Automata.
- Authors
Madejski, Grzegorz; Szepietowski, Andrzej
- Abstract
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.
- Subjects
FINITE state machines; TURING machines; NP-complete problems; MACHINE theory
- Publication
International Journal of Foundations of Computer Science, 2020, Vol 31, Issue 04, p527
- ISSN
0129-0541
- Publication type
Article
- DOI
10.1142/S0129054120500239