Logic in Computer Science (LICS 1992)

Paper: Deterministic vs. nondeterministic transitive closure logic (at LICS 1992)

Authors: Gradel, E. McColm, G.L.

Abstract

It is shown that transitive closure logic (FO+TC) is strictly more powerful than deterministic transitive closure logic (FO+DTC) on unordered structures. In fact, on certain classes of graphs, such as hypercubes or regular graphs of large degree and girth, every query in (FO+DTC) is first-order expressible. On the other hand, there are simple (FO+pos TC) queries on these classes that cannot be defined by first-order formulas

BibTeX

  @InProceedings{GradelMcColm-Deterministicvsnond,
    author = 	 {Gradel, E. and McColm, G.L.},
    title = 	 {Deterministic vs. nondeterministic transitive closure logic},
    booktitle =  {Proceedings of the Seventh Annual IEEE Symp. on Logic in Computer Science, {LICS} 1992},
    year =	 1992,
    editor =	 {Andre Scedrov},
    month =	 {June}, 
    pages =      {58--63},
    location =   {Santa Cruz, CA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }