Title :
Deterministic vs. nondeterministic transitive closure logic
Author :
Grädel, Erich ; McColm, Gregory L.
Author_Institution :
Math. Inst., Basel Univ., Switzerland
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
Keywords :
computational complexity; formal logic; graph theory; graphs; hypercubes; query; transitive closure logic; Database languages; Hypercubes; Logic; Microwave integrated circuits; Turing machines;
Conference_Titel :
Logic in Computer Science, 1992. LICS '92., Proceedings of the Seventh Annual IEEE Symposium on
Conference_Location :
Santa Cruz, CA
Print_ISBN :
0-8186-2735-2
DOI :
10.1109/LICS.1992.185519
