Path: utzoo!utgpu!water!watmath!clyde!att-cb!osu-cis!tut.cis.ohio-state.edu!husc6!uwvax!dogie!uwmcsd1!ig!agate!ucbvax!SVAX.CS.CORNELL.EDU!siegel From: siegel@SVAX.CS.CORNELL.EDU (Alexander Siegel) Newsgroups: comp.theory Subject: Maze searching problem Message-ID: <8804071921.AA08296@jade.berkeley.edu> Date: 7 Apr 88 18:53:13 GMT Sender: daemon@ucbvax.BERKELEY.EDU Reply-To: TheoryNet List , Alexander Siegel Distribution: inet Organization: The Internet Lines: 21 You are given a graph. Each graph in the maze is labelled with a name of size O(log n). The graph has the following properties: 1. Each edge is labelled with an arrow but it can be traversed either direction. 2. The directed graph formed by the arrows is acyclic, and the in and out-degree if each vertex is at most 2. 3. One vertex is the start and one is the goal. The problem is determine whether the goal is reachable from the start within an O(log n) space bound and no time bound. Note: an equivalent problem is to produce a new graph such that the only vertex with in-degree 0 is the start, and the head can only move to the right on the output tape. -- Alex Siegel (607)255-1165 (Low Bandwidth Audio) 4161 Upson Hall, Cornell University, Ithaca NY 14853 (Hard Copy) siegel@svax.cs.cornell.edu (ARPAnet) siegel@CRNLCS (BITNET) {uw-beaver,ihnp4,decvax,vax135}!cornell!siegel (UUCP)