Abstract
We present Ehrenfeucht-Fraïssé games for transitive closure logic (FO + TC) and for quantifier classes in (FO + TC). With this method we investigate the fine structure of positive transitive closure logic (FO + pos TC), and identify an infinite quantifier hierarchy inside (FO + pos TC), formed by interleaving universal quantifiers and TC-operators.
It is also shown that transitive closure logic (and its fragments) have the same expressive power as the linear programs in certain extensions of Datalog.
Preview
Unable to display preview. Download preview PDF.
References
F. Afrati and S. Cosmadakis, Expressiveness of Restricted Recursive Queries, Proceedings of 21st ACM Symposium on Theory of Computing (1989), 113–126.
F. Afrati, S. Cosmadakis and M. Yannakakis, On Datalog vs. Polynomial Time, Proceedings of 10th ACM Symposium on Principles of Database Systems (1991).
J. Barwise, On Moschovakis closure ordinals, J. Symbolic Logic 42 (1977), 292–296.
J. Cai, M. Fürer and N. Immerman, An Optimal Lower Bound on the Number of Variables for Graph Identification, Proceedings of 30th IEEE Symposium on Foundations of Computer Science (1989), 612–617.
A. Chandra and D. Harel, Structure and Complexity of Relational Queries, J. Comp. Syst. Sciences 25 (1982), 99–128.
A. Chandra and D. Harel, Horn Clause Queries and Generalizations, J. Logic Programming 1 (1985), 1–15.
M. Consens and A. Mendelzon, GraphLog: a Visual Formalism for Real Life Recursion, Proceedings of 9th ACM Symposium on Principles of Database Systems (1990), 404–416.
E. Dahinaus, Skolem Normal Forms Concerning the Least Fixed Point, in: “Computation Theory and Logic” (E. Börger, Ed.), Lecture Notes in Computer Science Nr. 270, Springer 1987, 101–106.
H. D. Ebbinghaus, J. Flum and W. Thomas, Mathematical Logic, Springer-Verlag, 1984.
A. Ehrenfeucht, An application of games to the completeness problem for formalized theories, Fund. Math. 49 (1961) 129–141.
R. Fagin, Monadic generalized spectra, Zeitschrift für Math. Logik Grundlagen d. Math. 21 (1975), 89–96.
R. Fraïssé, Sur quelques classifications des systèmes de relations, Publications Scientifique de l' Université d' Alger, Série A 1 (1954), 35–182.
E. Grädel and G. McColm, Hierarchies in Transitive Closure Logic, Stratified Datalog and Infinitary Logic, in preparation.
Y. Gurevich, Logic and the Challenge of Computer Science, in: E. Börger (Ed.), Trends in Theoretical Computer Science, Computer Science Press (1988), 1–57.
N. Immerman, Number of Quantifiers is Better than Number of Tape Cells, J. Comp. Syst. Sciences 22 (1981), 65–72.
N. Immerman, Upper and lower bounds for first-order expressibility, J. Comp. Syst. Sciences 25 (1982), 76–98.
N. Immerman, Languages that Capture Complexity Classes, SIAM J. Comput. 16 (1987), 760–778.
N. Immerman, Nondeterministic space is closed under complementation, SIAM J. Comput. 17 (1988), 935–939.
N. Immerman, Descriptive and Computational Complexity, in: J. Hartmanis (Ed.), Computational Complexity Theory, Proc. of AMS Symposia in Appl. Math. 38 (1989), 75–91.
P. Kannellakis, Elements of Relational Database Theory, in: J. van Leeuwen (Ed.), Handbook of Theoretical Computer Science, vol. B, North Holland, Amsterdam 1990, pp. 1073–1156.
Ph. Kolaitis, The Expressive Power of Stratified Logic Programs, Information and Computation 90 (1991), 50–66.
Ph. Kolaitis and M. Vardi, On the Expressive Power of Datalog: Tools and a Case Study, Proceeding of 9th ACM Symposium on Principles of Database Systems (1990), 61–71.
Ph. Kolaitis and M. Vardi, 0-1 Laws for Infinitary Logics, Proceedings of 5th IEEE Symposium on Logic in Computer Science (1990), 156–167.
V. Lakshmanan and A. Mendelzon, Inductive pebble games and the expressive power of datalog, Proceedings of 8th ACM Symposium on Principles of Database Systems (1989), 301–310.
R. Szelepcsényi, The Method of Forced Enumeration for Nondeterministic Automata, Acta Informatica 26, (1988), 279–284.
A. Van Gelder, Negation as Failure using tight derivations for general logic programs, Proceedings of 3rd IEEE Symposium on Logic Programming (1986), 137–146.
M. Zloof, Query-by-Example: Operations on the Transitive Closure, IBM Research Report RC5526 (1976).
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1992 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Grädel, E. (1992). On transitive closure logic. In: Börger, E., Jäger, G., Kleine Büning, H., Richter, M.M. (eds) Computer Science Logic. CSL 1991. Lecture Notes in Computer Science, vol 626. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0023764
Download citation
DOI: https://doi.org/10.1007/BFb0023764
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-55789-0
Online ISBN: 978-3-540-47285-8
eBook Packages: Springer Book Archive