• DocumentCode
    2366703
  • Title

    Space bounds for graph connectivity problems on node-named JAGs and node-ordered JAGs

  • Author

    Poon, C.K.

  • Author_Institution
    Dept. of Comput. Sci., Toronto Univ., Ont., Canada
  • fYear
    1993
  • fDate
    3-5 Nov 1993
  • Firstpage
    218
  • Lastpage
    227
  • 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;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Foundations of Computer Science, 1993. Proceedings., 34th Annual Symposium on
  • Conference_Location
    Palo Alto, CA
  • Print_ISBN
    0-8186-4370-6
  • Type

    conf

  • DOI
    10.1109/SFCS.1993.366865
  • Filename
    366865
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2366703