| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 6873834 | Information and Computation | 2018 | 8 Pages |
Abstract
An accepting run in a two-way finite automaton M is a sequence of states that M enters during some accepting computation. The set of all such runs is denoted by Lrun,M. We study the complexity of Lrun,M when M is a 2NFA (2DFA). We also look at the complexity of “position sampling” (the sequence of states that M enters in specified positions of some accepted input) in a 2NFA. In particular, we give some language properties of sampled runs of 2NFAs augmented with restricted unbounded storage.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Oscar H. Ibarra, Zhe Dang, Qin Li,