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} }