Accepting runs in a two-way finite automaton

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.