Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
  1. Home
  2. Books
  3. Bounded Variable Logics and Counting
  • Cited by 14
  • Martin Otto, Rheinisch-Westfälische Technische Hochschule, Aachen, Germany
Publisher:
Cambridge University Press
Online publication date:
March 2017
Print publication year:
2017
Online ISBN:
9781316716878
DOI:
https://doi.org/10.1017/9781316716878
Subjects:
Mathematics, Logic, Categories and Sets, Logic, Philosophy, Programming Languages and Applied Logic
Series:
Lecture Notes in Logic (9)
Information

Book description

Since their inception, the Perspectives in Logic and Lecture Notes in Logic series have published seminal works by leading logicians. Many of the original books in the series have been unavailable for years, but they are now in print once again. In this volume, the ninth publication in the Lecture Notes in Logic series, Martin Otto gives an introduction to finite model theory that indicates the main ideas and lines of inquiry that motivate research in this area. Particular attention is paid to bounded variable infinitary logics, with and without counting quantifiers, related fixed-point logics, and the corresponding fragments of Ptime. The relations with Ptime exhibit the fruitful exchange between ideas from logic and from complexity theory that is characteristic of finite model theory.

Refine List

Actions for selected content:

Select all | Deselect all
  • View selected items
  • Export citations
  • Download PDF (zip)
  • Save to Kindle
  • Save to Dropbox
  • Save to Google Drive

Save Search

You can save your searches here and later view and run them again in "My saved searches".

Please provide a title, maximum of 40 characters.
Cancel
×

Contents

Contents
References
Bibliography
Abiteboul, S. and Vianu, V.. Fixpoint extensions of first-order logic and Datalog-like languages. In Proc. 4th IEEE Symp. on Logic in Computer Science, pages 71–79, 1989.
Abiteboul, S. and Vianu, V.. Generic computation and its complexity. In Proc. 23rd ACM Symp. on Theory of Computing, pages 209–219, 1991.
Babai, L., Erdös, P., and Selkow, M.. Random graph isomorphism. SIAM Journal of Computing, 9:628–635, 1980.
Babai, L. and Kučera, L.. Canonical labellings of graphs in linear average time. In Proc. 21st IEEE Symp. on Foundations of Computer Science, pages 39–46, 1980.
Barwise, J.. On Moschovakis closure ordinals. Journal of Symbolic Logic, 42:292–296, 1977.
Blass, A. and Gurevich, Y.. Equivalence relations, invariants, and normal forms, II. In Börger, E., Hasenjäger, G. and Rödding, D., editors, Logic and Machines: Decision Problems and Complexity, Lecture Notes in Computer Science 171, pages 24–42. Springer-Verlag, 1984.
Börger, E., Grädel, E., and Gurevich, Y.. The Classical Decision Problem, Perspectives in Mathematical Logic, Springer-Verlag, 1996.
Büchi, J. R.. Weak second-order arithmetic and finite automata. Z. Math. Logik Grundlagen Math., 6:66–92, 1960.
Cai, J., Fürer, M., and Immerman, N.. An optimal lower bound on the number of variables for graph identification. In Proc. 30th IEEE Symp. on Foundations of Computer Science, pages 612–617, 1989.
Cai, J., Fürer, M., and Immerman, N.. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12:389–410, 1992.
Chandra, A. and Harel, D.. Computable queries for relational databases. Journal of Computer and System Sciences, 21:156–178, 1980.
Chandra, A. and Harel, D.. Structure and complexity of relational queries. Journal of Computer and System Sciences, 25:99–128, 1982.
Dahlhaus, E.. Skolem normal forms concerning the least fixpoint. In Börger, E., editor, Computation Theory and Logic, Lecture Notes in Computer Science 270, pages 101–106. Springer-Verlag, 1987.
Dawar, . Feasible computation through model theory. PhD thesis, University of Pennsylvania, 1993.
Dawar, A.. Generalized quantifiers and logical reducibilities. Journal of Logic and Computation, 5:213–226, 1995.
Dawar, A.. A restricted second-order logic for finite structures. In Leivant, D., editor, Logic and Computational Complexity, pages 393–413. Springer-Verlag, 1995.
Dawar, A. and Hella, L.. The expressive power of finitely many generalized quantifiers. In Proc. 9th IEEE Symp. on Logic in Computer Science, pages 20–29, 1994.
Dawar, A., Lindell, S., and Weinstein, S.. Infinitary logic and inductive definability over finite structures. Information and Computation, 119:160–175, 1995.
Ebbinghaus, H.-D.. Extended logics: the general framework. In Barwise, J. and Feferman, S., editors, Model-Theoretic Logics, pages 25–76. Springer-Verlag, 1985.
Ebbinghaus, H.-D. and Flum, J.. Finite Model Theory. Perspectives in Mathematical Logic, Springer-Verlag, 1995.
Ebbinghaus, H.-D., Flum, J., and Thomas, W.. Mathematical Logic. Springer-Verlag, 2nd edition, 1994.
Elgot, C.. Decision problems of finite-automata design and related arithmetics. Trans. Amer. Math. Soc., 98:21–51, 1961.
Fagin, R.. Generalized first-order spectra and polynomial-time recognizable sets. In Karp, R. M., editor, Complexity of Computation, SIAM-AMS Proceedings, Vol. 7, pages 43–73, 1974.
Fagin, R.. Finite-model theory — a personal perspective. In Abiteboul, S. and Kanellakis, P., editors, Proc. 1990 International Conference on Database Theory, Lecture Notes in Computer Science 470, pages 3–24. Springer-Verlag, 1990. Also in Theoretical Computer Science, 116:3–31, 1993.
Grädel, E. and Gurevich, Y.. Tailoring recursion for complexity. Journal of Symbolic Logic, 60:952–969, 1995.
Grädel, E. and Gurevich, Y.. Metafinite model theory. In Leivant, D., editor, Logic and Computational Complexity, pages 313–366. Springer-Verlag, 1995.
Grädel, E., Kolaitis, Ph. G., and Vardi, M. Y.. On the decison problem for two-variable first-order logic. Submitted, 1996.
Grädel, E. and Otto, M.. Inductive definability with counting on finite structures. In Börger, E. et al., editors, Computer Science Logic, CSL –92, Selected Papers, Lecture Notes in Computer Science 702, pages 231— 247. Springer-Verlag, 1993.
Grädel, E., Otto, M., and Rosen, E.. Undecidability results on two-variable logics. Preprint, 1996.
Grädel, E., Otto, M., and Rosen, E.. Two-variable logic with counting is decidable. Preprint, 1996.
Grohe, M.. Complete problems for fixed-point logics. Journal of Symbolic Logic, 60:517–527, 1995.
Gurevich, Y.. Toward logic tailored for computational complexity. In Richter, M. M. et al., editors, Computation and Proof Theory, Lecture Notes in Mathematics 1104, pages 175–216. Springer-Verlag, 1984.
Gurevich, Y.. Logic and the challenge of computer science. In Börger, , editor, Current Trends in Theoretical Computer Science, pages 1–57. Computer Science Press, 1988.
Gurevich, Y. and Shelah, S.. Fixed-point extensions of first-order logic. Annals of Pure and Applied Logic, 32:265–280, 1986.
Gurevich, Y. and Shelah, S.. On finite rigid structures. Journal of Symbolic Logic, 61:549–562, 1996.
Härtig, H.. Über einen Quantifikator mit zwei Wirkungsbereichen. In Kalmar, L., editor, Collogue sur les Fondements des Mathematiques, les Machines Mathematiques, et leur Applications, pages 31–36, 1965.
Immerman, N.. Number of quantifiers is better than number of tape cells. Journal of Computer and System Sciences, 22:384–406, 1981.
Immerman, N.. Upper and lower bounds for first-order expressibility. Journal of Computer and System Sciences, 25:76–98, 1982.
Immerman, N.. Relational queries computable in polynomial time. Information and Control, 68:86–104, 1986.
Immerman, N.. Expressibility as a complexity measure: results and directions. In Proc. 2nd Structure in Complexity Conference, pages 194—202, 1987.
Immerman, N.. Languages that capture complexity classes. SIAM Journal of Computing, 16:760–778, 1987.
Immerman, N.. Descriptive and computational complexity. In Hartmanis, J., editor, Computational Complexity Theory, Proc. Symp. Applied Math., Vol. 38, pages 75–91. American Mathematical Society, 1989.
Immerman, N. and Lander, E. S.. Describing graphs: a first-order approach to graph canonization. In Selman, A., editor, Complexity Theory Retrospective, pages 59–81. Springer-Verlag, 1990.
Kolaitis, Ph. G. and Väänänen, J.. Generalized quantifiers and pebble games on finite structures. Annals of Pure and Applied Logic, 74:23–75, 1995.
Kolaitis, Ph. G. and Vardi, M. Y.. Infinitary logics and 0–1 laws. Information and Computation, 98:258–294, 1992.
Kolaitis, Ph. G. and Vardi, M. Y.. Fixpoint logic vs. infinitary logic in finite-model theory. In Proc. 7th IEEE Symp. on Logic and Computer Science, pages 46–57, 1992.
Leivant, D.. Inductive definitions over finite structures. Information and Computation, 89:95–108, 1990.
Mortimer, M.. On languages with two variables. In Math, Z.. Logik und Grundlagen Math., 21:135–140, 1975.
Otto, M.. Generalized quantifiers for simple properties. In Proc. 9th IEEE Symp. on Logic and Computer Science, pages 30–39, 1994.
Otto, M.. Ptime canonization for two variables with counting. In Proc. 10th IEEE Symp. on Logic and Computer Science, pages 342–352, 1995.
Otto, M.. Canonization for two variables and puzzles on the square. To appear in Annals of Pure and Applied Logic.
Otto, M.. The expressive power of fixed-point logic with counting. Journal of Symbolic Logic, 61:147–176, 1996.
Otto, M.. Bounded-variable logics: two, three, and more. Preprint, 1996.
Papadimitiou, C. H.. Computational Complexity. Addison-Wesley Publishing Company, 1995.
Poizat, B.. Deux ou trois choses que je sais de Ln. Journal of Symbolic Logic, 47:641–658, 1982.
Rescher, N.. Plurality quantification. Journal of Symbolic Logic, 27:373–374, 1962.
Scott, D.. A decision method for validity of sentences in two variables. Journal of Symbolic Logic, 27:377, 1962.
Trakhtenbrot, B.. Finite automata and the logic of monadic predicates, (in Russian) Dokl. Akad. Nauk SSSR, 140:326–329, 1961.
Vardi, M. Y.. The complexity of relational query languages. 14th ACM Symp. on Theory of Computing, pages 137–146, 1982.
Wegener, I.. The Complexity of Boolean Functions. John Wiley and Teubner, 1987.

Metrics

Full text views

Total number of HTML views: 0
Total number of PDF views: 0 *
Loading metrics...

Book summary page views

Total views: 0 *
Loading metrics...

* Views captured on Cambridge Core between #date#. This data will be updated every 24 hours.

Usage data cannot currently be displayed.