NSPARQL Jesse Weaver 20080911 Jesse Weaver

Question is for the Presentation: nSPARQL Jesse Weaver 20080911
Question is asked by: Jesse Weaver
The Question is: The conclusion of time complexity O(G*exp) seems to be based on the assumption that each call to Label does some fraction of G*Di(exp) work. However, accounting for lines 5-6 of Label seems less intuitive as the proof for theorem one states only that a depth-first search could be used. Generally, a depth-first search runs in O(V+E) time for a given graph G0=(V,E). V seems like it could be O(G*exp) (exp local to Label), but how do we account for E? Furthermore, do we have to run this depth-first search for every (u,q0) in the product automaton? Am I missing something? Is there some aspect of the nature of the product automaton that I'm overlooking?

Question asked	The conclusion of time complexity O(Gexp) … The conclusion of time complexity O(Gexp) seems to be based on the assumption that each call to Label does some fraction of GDi(exp) work. However, accounting for lines 5-6 of Label seems less intuitive as the proof for theorem one states only that a depth-first search could be used. Generally, a depth-first search runs in O(V+E) time for a given graph G0=(V,E). V seems like it could be O(Gexp) (exp local to Label), but how do we account for E? Furthermore, do we have to run this depth-first search for every (u,q0) in the product automaton? Am I missing something? Is there some aspect of the nature of the product automaton that I'm overlooking? he product automaton that I'm overlooking?
Question asked by	Jesse Weaver +
Question for the Presentation	NSPARQL Jesse Weaver 20080911 +