We investigate reachability problems on different types of labeled graphs constrained to formal languages from a family
. If every language in
is accepted by a one-way nondeterministic storage automaton, then we give an appealing characterization of the computational complexity of the labeled graph reachability problem in terms of two-way nondeterministic storage automata with auxiliary worktape that is logarithmic-space bounded. Moreover, we also consider acyclic graphs in the underlying reachability instance, obtaining a lower bound result for auxiliary storage automata that are simultaneously space and time restricted.
Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten