Title :
Space bounds for graph connectivity problems on node-named JAGs and node-ordered JAGs
Author_Institution :
Dept. of Comput. Sci., Toronto Univ., Ont., Canada
Abstract :
Two new models, NO-JAG and NN-JAG in order of increasing computation power, are introduced as extensions to the conventional JAG model. A space lower bound of Ω(log2 n/log log n) is proved for the problem of directed st-connectivity on a probabilistic NN-JAG and a space upper bound of O(log n) is proved for the problem of directed st-nonconnectivity on a nondeterministic NO-JAG. It is also shown that a nondeterministic NO-JAG is nearly as powerful as a nondeterministic Turing machine
Keywords :
Turing machines; automata theory; computational complexity; graph theory; probabilistic automata; graph connectivity problems; node-named JAGs; node-ordered JAGs; nondeterministic NO-JAG; nondeterministic Turing machine; space bounds; Automata; Binary decision diagrams; Computer science; Search problems; Turing machines; Upper bound;
Conference_Titel :
Foundations of Computer Science, 1993. Proceedings., 34th Annual Symposium on
Conference_Location :
Palo Alto, CA
Print_ISBN :
0-8186-4370-6
DOI :
10.1109/SFCS.1993.366865
