Nodes connected by path languages

Markus Holzer, Martin Kutrib, and Ursula Leiter

Abstract. We investigate reachability problems on different types of labeled graphs constrained to formal languages from a family L. If every language in L 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.

Comments are closed.